Logo
Unionpedia
Comunicación
Disponible en Google Play
¡Nuevo! ¡Descarga Unionpedia en tu dispositivo Android™!
Descargar
¡Más rápido que el navegador!
 

EXPTIME

Índice EXPTIME

En teoría de la complejidad computacional, la clase de complejidad EXPTIME (también llamada EXP) es el conjunto de los problemas de decisión que pueden ser resueltos en una máquina de Turing determinista en tiempo O(2p(n)), donde p(n) es una función polinomial sobre n. En términos de DTIME, Se sabe que y por el teorema de la jerarquía temporal: de manera que al menos una de las inclusiones de la primera línea debe ser estricta (se piensa que todas esas inclusiones son estrictas).

27 relaciones: Algoritmo de aproximación, Axis: Bold as Love, Clase de complejidad, Clases de complejidad P y NP, Complejidad en los juegos, Complejidad parametrizada, Complejidad temporal, Corrección de errores hacia adelante, Criptoanálisis, E (clase de complejidad), ELEMENTARY, EXPSPACE, Factorización de curva elíptica de Lenstra, Go y matemáticas, Jerarquía polinómica, Juego generalizado, La mujer perfecta (telenovela), Lógica de descripción, Máquina de Turing alternante, P/poly, Problema del viajante, PSPACE-completo, ReDoS, Teoría de la complejidad computacional, Teorema de la jerarquía temporal, Tiempo de ejecución, Transformación polinómica.

Algoritmo de aproximación

En ciencias de la computación e investigación de operaciones, un algoritmo de aproximación es un algoritmo usado para encontrar soluciones aproximadas a problemas de optimización.

¡Nuevo!!: EXPTIME y Algoritmo de aproximación · Ver más »

Axis: Bold as Love

Axis: Bold as Love es el segundo álbum de The Jimi Hendrix Experience, lanzado en 1967 por Track Records.

¡Nuevo!!: EXPTIME y Axis: Bold as Love · Ver más »

Clase de complejidad

En teoría de la complejidad computacional, una clase de complejidad es un conjunto de problemas de decisión de complejidad relacionada.

¡Nuevo!!: EXPTIME y Clase de complejidad · Ver más »

Clases de complejidad P y NP

La relación entre las clases de complejidad NP y P es una pregunta por primera vez formulada por el científico computacional Stephen Cook que la teoría de la complejidad computacional aún no ha podido responder.

¡Nuevo!!: EXPTIME y Clases de complejidad P y NP · Ver más »

Complejidad en los juegos

La teoría de juegos combinatorios posee diversas maneras de medir la complejidad en los juegos.

¡Nuevo!!: EXPTIME y Complejidad en los juegos · Ver más »

Complejidad parametrizada

En ciencias de la computación, la complejidad parametrizada es una rama de la teoría de la complejidad computacional que se centra en la clasificación de problemas computacionales de acuerdo a su dificultad con respecto a varios parámetros de la entrada.

¡Nuevo!!: EXPTIME y Complejidad parametrizada · Ver más »

Complejidad temporal

En informática, la complejidad temporal es la complejidad computacional que describe la cantidad de tiempo que lleva ejecutar un algoritmo.

¡Nuevo!!: EXPTIME y Complejidad temporal · Ver más »

Corrección de errores hacia adelante

En telecomunicaciones, teoría de la información y teoría de la codificación, la corrección de errores hacia adelante (en inglés, forward error correction o FEC) o codificación de canal es una técnica utilizada para controlar los errores en la transmisión de datos a través de canales de comunicación poco fiables o ruidosos.

¡Nuevo!!: EXPTIME y Corrección de errores hacia adelante · Ver más »

Criptoanálisis

El criptoanálisis (del griego kryptós, 'escondido' y analýein, 'desatar') es la parte de la criptología que se dedica al estudio de sistemas criptográficos con el fin de encontrar debilidades en los sistemas y romper su seguridad sin el conocimiento de información secreta.

¡Nuevo!!: EXPTIME y Criptoanálisis · Ver más »

E (clase de complejidad)

En complejidad computacional, la clase de complejidad E es el conjunto de problemas de decisión que pueden ser resueltos por una Máquina de Turing determinista en tiempo 2O(n), y es por lo tanto igual a la clase de complejidad DTIME(2O(n)).

¡Nuevo!!: EXPTIME y E (clase de complejidad) · Ver más »

ELEMENTARY

En teoría de la complejidad computacional, la clase de complejidad ELEMENTARY de las funciones recursivas elementales es la unión de las clases El nombre fue acuñado por László Kalmár, en el contexto de funciones recursivas e indecidibilidad; a pesar de su nombre, la mayoría de problemas en esta clase distan mucho de ser elementales.

¡Nuevo!!: EXPTIME y ELEMENTARY · Ver más »

EXPSPACE

En teoría de la complejidad computacional, la clase de complejidad EXPSPACE es el conjunto de los problemas de decisión que pueden ser resueltos con una máquina de Turing determinista en espacio O(2p(n)), donde p(n) es una función polinomial sobre n. De acuerdo con el Teorema de Savitch, esta clase es igual a la que considera máquinas de Turing no deterministas.

¡Nuevo!!: EXPTIME y EXPSPACE · Ver más »

Factorización de curva elíptica de Lenstra

La factorización de curva elíptica de Lenstra o método de factorización de curva elíptica (del inglés elliptic curve factorization method, ECM) es un rápido algoritmo de tiempo de ejecución sub-exponencial para la factorización de enteros que emplea curvas elípticas.

¡Nuevo!!: EXPTIME y Factorización de curva elíptica de Lenstra · Ver más »

Go y matemáticas

El juego de go es uno de los juegos más populares del mundo.

¡Nuevo!!: EXPTIME y Go y matemáticas · Ver más »

Jerarquía polinómica

En teoría de complejidad computacional, la jerarquía polinómica (a veces llamada  jerarquía de tiempo polinómico) es una jerarquía de clases de complejidad que generaliza las clases P, NP y co-NP a máquinas de oráculo. Es una contrapartida de recurso-acotado a la jerarquía aritmética y jerarquía analítica de la lógica matemática.

¡Nuevo!!: EXPTIME y Jerarquía polinómica · Ver más »

Juego generalizado

En la teoría de la complejidad computacional, un juego generalizado es un juego o rompecabezas que se ha generalizado para que se pueda jugar en un tablero o cuadrícula de cualquier tamaño.

¡Nuevo!!: EXPTIME y Juego generalizado · Ver más »

La mujer perfecta (telenovela)

La mujer perfecta es Diana tiffer venezolana producida y transmitida por Venevisión en el año 2010.

¡Nuevo!!: EXPTIME y La mujer perfecta (telenovela) · Ver más »

Lógica de descripción

Las lógicas de descripción, también llamadas lógicas descriptivas (DL por description logics) son una familia de lenguajes de representación del conocimiento que pueden ser usados para representar conocimiento terminológico de un dominio de aplicación de una forma estructurada y formalmente bien comprendida.

¡Nuevo!!: EXPTIME y Lógica de descripción · Ver más »

Máquina de Turing alternante

En la teoría de la complejidad computacional, una máquina de Turing alternante (ATM) es una máquina de Turing no determinista (NTM) con una regla para la aceptación de cómputos que generaliza las reglas usadas en la definición de las clases de complejidad NP y co-NP.

¡Nuevo!!: EXPTIME y Máquina de Turing alternante · Ver más »

P/poly

En la teoría de la complejidad computacional, P/poly es la clase de complejidad de los lenguajes reconocidos por una máquina de Turing de tiempo polinomial con una función de asesoramiento limitada polinomialmente.

¡Nuevo!!: EXPTIME y P/poly · Ver más »

Problema del viajante

El problema del vendedor viajero (problema del vendedor ambulante, problema del agente viajero o problema del viajante, PCP, TSP por sus siglas en inglés, Travelling Salesman Problem) responde a la siguiente pregunta: dada una lista de ciudades y las distancias entre cada par de ellas, ¿cuál es la ruta más corta posible que visita cada ciudad exactamente una vez y al finalizar regresa a la ciudad origen? Este es un problema NP-Hard dentro en la optimización combinatoria, muy importante en investigación operativa y en ciencias de la computación.

¡Nuevo!!: EXPTIME y Problema del viajante · Ver más »

PSPACE-completo

En teoría de la complejidad computacional, la clase de complejidad PSPACE-completo (PSPACE-complete en inglés) es el subconjunto de los problemas de decisión en PSPACE y todo problema en PSPACE puede ser reducido a él en tiempo polinomial.

¡Nuevo!!: EXPTIME y PSPACE-completo · Ver más »

ReDoS

Una denegación de servicio de expresión regular o regular expression denial of service (ReDoS), por sus siglas en inglés.

¡Nuevo!!: EXPTIME y ReDoS · Ver más »

Teoría de la complejidad computacional

La teoría de la complejidad computacional o teoría de la complejidad informática es una rama de la teoría de la computación que se centra en la clasificación de los problemas computacionales de acuerdo con su dificultad inherente, y en la relación entre dichas clases de complejidad.

¡Nuevo!!: EXPTIME y Teoría de la complejidad computacional · Ver más »

Teorema de la jerarquía temporal

En la teoría de complejidad computacional, los teoremas de jerarquía temporal son declaraciones importantes sobre cómputo de tiempo acotado en máquinas de Turing.

¡Nuevo!!: EXPTIME y Teorema de la jerarquía temporal · Ver más »

Tiempo de ejecución

Se denomina tiempo de ejecución (runtime en inglés) al intervalo de tiempo en el que un programa de computadora se ejecuta en un sistema operativo.

¡Nuevo!!: EXPTIME y Tiempo de ejecución · Ver más »

Transformación polinómica

En complejidad computacional, una transformación polinómica, reducción polinómica o reducción de Karp, es una manera de relacionar dos problemas de decisión, de manera que la existencia de un algoritmo que resuelve el primer problema, garantiza inmediatamente, y a través de un tiempo polinómico, la existencia de un algoritmo que resuelve el segundo.

¡Nuevo!!: EXPTIME y Transformación polinómica · Ver más »

Redirecciona aquí:

EXP, Tiempo exponencial.

SalienteEntrante
¡Hey! ¡Ahora tenemos Facebook! »