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

EXPTIME y Máquina de Turing

Accesos rápidos: Diferencias, Similitudes, Coeficiente de Similitud Jaccard, Referencias.

Diferencia entre EXPTIME y Máquina de Turing

EXPTIME vs. Máquina de Turing

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). Una máquina de Turing es un dispositivo que manipula símbolos sobre una tira de cinta de acuerdo con una tabla de reglas.

Similitudes entre EXPTIME y Máquina de Turing

EXPTIME y Máquina de Turing tienen 5 cosas en común (en Unionpedia): Algoritmo, NP (clase de complejidad), P (clase de complejidad), Problema de la parada, Teoría de la complejidad computacional.

Algoritmo

En matemáticas, lógica, ciencias de la computación y disciplinas relacionadas, un algoritmo (probablemente del latín tardío algorithmus, y este del árabe clásico ḥisābu lḡubār, que significa «cálculo mediante cifras arábigas») es un conjunto de instrucciones o reglas definidas y no-ambiguas, ordenadas y finitas que permite, típicamente, solucionar un problema, realizar un cómputo, procesar datos y llevar a cabo otras tareas o actividades.

Algoritmo y EXPTIME · Algoritmo y Máquina de Turing · Ver más »

NP (clase de complejidad)

En teoría de la complejidad computacional, NP es el acrónimo en inglés de nondeterministic polynomial time ("tiempo polinomial no determinista").

EXPTIME y NP (clase de complejidad) · Máquina de Turing y NP (clase de complejidad) · Ver más »

P (clase de complejidad)

En computación, cuando el tiempo de ejecución de un algoritmo (mediante el cual se obtiene una solución al problema) es menor o igual que un cierto valor calculado a partir del número de variables implicadas (generalmente variables de entrada) usando una fórmula polinómica, se dice que dicho problema se puede resolver en un tiempo polinómico o polinomial P. La tesis de Cobham postula que la clase P es la que tiene los problemas tratables más grandes, es decir, los problemas de gran tamaño que se pueden calcular de forma eficiente con un ordenador.

EXPTIME y P (clase de complejidad) · Máquina de Turing y P (clase de complejidad) · Ver más »

Problema de la parada

El problema de la parada o problema de la detención para máquinas de Turing consiste en lo siguiente: dada una Máquina de Turing M y una palabra w, determinar si M terminará en un número finito de pasos cuando es ejecutada usando w como dato de entrada.

EXPTIME y Problema de la parada · Máquina de Turing y Problema de la parada · 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.

EXPTIME y Teoría de la complejidad computacional · Máquina de Turing y Teoría de la complejidad computacional · Ver más »

La lista de arriba responde a las siguientes preguntas

Comparación de EXPTIME y Máquina de Turing

EXPTIME tiene 22 relaciones, mientras Máquina de Turing tiene 60. Como tienen en común 5, el índice Jaccard es 6.10% = 5 / (22 + 60).

Referencias

En este artículo se encuentra la relación entre EXPTIME y Máquina de Turing. Si desea acceder a cada artículo del que se extrajo la información visite:

¡Hey! ¡Ahora tenemos Facebook! »