En la teoría de la complejidad computacional , la clase de complejidad NEXPTIME (a veces llamada NEXP ) es el conjunto de problemas de decisión que pueden ser resueltos por una máquina de Turing no determinista usando el tiempo..
En términos de NTIME ,
Alternativamente, NEXPTIME se puede definir utilizando máquinas de Turing deterministas como verificadores. Un lenguaje L es en NEXPTIME si y sólo si existen polinomios p y q , y una máquina de Turing determinista M , de tal manera que
- Para todos x y y , la máquina M se ejecuta en tiempo en la entrada
- Para todo x en L , existe una cadena y de longitud tal que
- Para todo x no en L y todas las cadenas y de longitud,
Sabemos
y también, por el teorema de la jerarquía temporal , que
- NP ⊊ PRÓXIMO
Si P = NP , entonces NEXPTIME = EXPTIME ( argumento de relleno ); más precisamente, E ≠ NE si y sólo si existen lenguas dispersas en NP que no están en P . [1]
Caracterizaciones alternativas
NEXPTIME a menudo surge en el contexto de los sistemas de prueba interactivos , donde hay dos caracterizaciones principales del mismo. El primero es el sistema de prueba MIP , donde tenemos dos probadores todopoderosos que se comunican con un verificador de tiempo polinomial aleatorio (pero no entre sí). Si la cadena está en el idioma, deben poder convencer al verificador de esto con alta probabilidad. Si la cadena no está en el idioma, no deben poder engañar en colaboración al verificador para que acepte la cadena, excepto con poca probabilidad. El hecho de que los sistemas de prueba MIP puedan resolver todos los problemas en NEXPTIME es bastante impresionante si tenemos en cuenta que cuando solo hay un probador presente, solo podemos reconocer todo PSPACE ; la capacidad del verificador para "contrainterrogar" a los dos probadores le confiere un gran poder. Consulte el sistema de prueba interactivo # MIP para obtener más detalles.
Otro sistema de prueba interactivo que caracteriza a NEXPTIME es una cierta clase de pruebas comprobables probabilísticamente . Recuerde que NP puede verse como la clase de problemas en los que un probador todopoderoso da una supuesta prueba de que una cadena está en el lenguaje, y una máquina determinista de tiempo polinomial verifica que es una prueba válida. Realizamos dos cambios a esta configuración:
- Agregue aleatoriedad, la capacidad de lanzar monedas, a la máquina verificadora.
- En lugar de simplemente dar la supuesta prueba al verificador en una cinta, déle acceso aleatorio a la prueba. El verificador puede especificar un índice en la cadena de prueba y recibir el bit correspondiente. Dado que el verificador puede escribir un índice de longitud polinomial, potencialmente puede indexar en una cadena de prueba exponencialmente larga.
Estas dos extensiones juntas amplían enormemente la potencia del sistema de pruebas, lo que le permite reconocer todos los idiomas en NEXPTIME . La clase se llama PCP (poli, poli). Además, en esta caracterización, el verificador puede limitarse a leer solo un número constante de bits, es decir, NEXPTIME = PCP (poli, 1). Consulte las pruebas comprobables probabilísticamente para obtener más detalles.
NEXPTIME-complete
Un problema de decisión es NEXPTIME-completo si está en NEXPTIME, y cada problema en NEXPTIME tiene una reducción de varios uno en tiempo polinómico . En otras palabras, existe un algoritmo de tiempo polinomial que transforma las instancias de una en instancias de la otra con la misma respuesta. Los problemas que se completan con NEXPTIME pueden considerarse los problemas más difíciles de NEXPTIME. Sabemos que los problemas NEXPTIME-complete no están en NP; Se ha comprobado que estos problemas no se pueden verificar en tiempo polinomial , mediante el teorema de la jerarquía temporal .
Un conjunto importante de problemas completos de NEXPTIME se relaciona con circuitos sucintos . Los circuitos sucintos son máquinas simples que se utilizan para describir gráficos en un espacio exponencialmente menor. Aceptan dos números de vértice como entrada y salida si hay un borde entre ellos. Si resolver un problema en un gráfico en una representación natural, como una matriz de adyacencia , es NP-completo , entonces resolver el mismo problema en una representación sucinta de circuito es NEXPTIME -completo, porque la entrada es exponencialmente más pequeña (bajo alguna condición leve que la reducción de NP-completitud se logra mediante una "proyección"). [2] [3] Como un ejemplo simple, encontrar una ruta hamiltoniana para un gráfico así codificado es NEXPTIME -complete.
Ver también
Referencias
- ^ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Conjuntos dispersos en NP-P: EXPTIME versus NEXPTIME. Información y control , volumen 65, número 2/3, págs. 158–181. 1985. En ACM Digital Library
- ^ C. Papadimitriou & M. Yannakakis , Una nota sobre representaciones sucintas de gráficos , Información y control, vol 71 num 3, diciembre de 1986, págs. 181-185, doi : 10.1016 / S0019-9958 (86) 80009-2
- ^ C. Papadimitriou. Complejidad computacional Addison-Wesley, 1994. ISBN 0-201-53082-1 . Sección 20.1, página 492.
- Complexity Zoo : NEXP , Complexity Zoo : coNEXP
- Arora, Sanjeev ; Barak, Boaz (2009), Computational Complexity: A Modern Approach , Cambridge , p. 57, ISBN 978-0-521-42426-4