PRÓXIMA HORA

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 resolverse mediante una máquina de Turing no determinista utilizando el tiempo . $2^{n^{O(1)}}$

En términos de NTIME ,

{\mathsf {NEXPTIME}}=\bigcup _{k\in \mathbb {N} }{\mathsf {NTIME}}(2^{n^{k}})

Alternativamente, NEXPTIME puede definirse utilizando máquinas de Turing deterministas como verificadores. Un lenguaje L está en NEXPTIME si y solo si existen polinomios p y q , y una máquina de Turing determinista M , tales que

Para todos los x e y , la máquina M se ejecuta a tiempo en la entrada $2^{p(|x|)}$ ${\estilo de visualización (x,y)}$
Para todo x en L , existe una cadena y de longitud tal que ⁠ ⁠ $2^{q(|x|)}$ $M(x,y)=1$
Para todo x no en L y todas las cadenas y de longitud , ⁠ ⁠ $2^{q(|x|)}$ $M(x,y)=0$

Nosotros sabemos

P ⊆ NP ⊆ TIEMPOEXP ⊆ TIEMPOEXP

y también, por el teorema de jerarquía temporal , que

NP ⊊ NEXPTIME

Si P = NP , entonces NEXPTIME = EXPTIME ( argumento de relleno ); más precisamente, $E \neq NE$ si y solo si existen lenguajes dispersos en NP que no están en P. ^[1]

Caracterizaciones alternativas

En complejidad descriptiva , los conjuntos de números naturales que se pueden reconocer en NEXPTIME son exactamente aquellos que forman el espectro de una oración , el conjunto de tamaños de modelos finitos de alguna oración lógica. ^[2]

NEXPTIME surge a menudo en el contexto de los sistemas de prueba interactivos , donde hay dos caracterizaciones principales de este. La primera 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 lenguaje, deben poder convencer al verificador de esto con alta probabilidad. Si la cadena no está en el lenguaje, no deben poder engañar colaborativamente al verificador para que acepte la cadena excepto con baja probabilidad. El hecho de que los sistemas de prueba MIP puedan resolver todos los problemas en NEXPTIME es bastante impresionante cuando consideramos que cuando solo está presente un probador, solo podemos reconocer todo PSPACE ; la capacidad del verificador de "interrogar" a los dos probadores le da un gran poder. Vea el sistema de prueba interactivo #MIP para más detalles.

Otro sistema de prueba interactivo que caracteriza a NEXPTIME es una determinada clase de pruebas que se pueden comprobar probabilísticamente . Recordemos que NP puede considerarse como la clase de problemas en los que un probador todopoderoso proporciona una supuesta prueba de que una cadena está en el lenguaje, y una máquina de tiempo polinomial determinista verifica que se trata de una prueba válida. Realizamos dos cambios en esta configuración:

Añade aleatoriedad y la capacidad de lanzar monedas a la máquina verificadora.
En lugar de simplemente entregar la supuesta prueba al verificador en una cinta, se le da 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 polinómica, 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 (poly, poly). Además, en esta caracterización, el verificador puede limitarse a leer solo una cantidad constante de bits, es decir, NEXPTIME = PCP (poly, 1). Consulte las pruebas que se pueden comprobar de forma probabilística para obtener más detalles.

NEXPTIME-completo

Un problema de decisión es NEXPTIME-completo si está en NEXPTIME, y cada problema en NEXPTIME tiene una reducción de muchos a uno en tiempo polinomial. En otras palabras, hay un algoritmo en tiempo polinomial que transforma instancias de uno en instancias del otro con la misma respuesta. Los problemas que son NEXPTIME-completos podrían considerarse como los problemas más difíciles en NEXPTIME. Sabemos que los problemas NEXPTIME-completos no están en NP; se ha demostrado que estos problemas no se pueden verificar en tiempo polinomial , mediante el teorema de jerarquía temporal .

Un conjunto importante de problemas NEXPTIME -completos se relaciona con circuitos sucintos . Los circuitos sucintos son máquinas simples que se utilizan para describir grafos en un espacio exponencialmente menor. Aceptan dos números de vértice como entrada y salida si hay una arista entre ellos. Si resolver un problema en un grafo en una representación natural, como una matriz de adyacencia , es NP-completo , entonces resolver el mismo problema en una representación de circuito sucinto es NEXPTIME -completo, porque la entrada es exponencialmente menor (bajo alguna condición leve de que la reducción de NP-completitud se logre mediante una "proyección"). ^[3]^[4] Como un ejemplo simple, encontrar un camino hamiltoniano para un grafo así codificado es NEXPTIME -completo.

Véase 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 la biblioteca digital de ACM
^ Jones, Neil D.; Selman, Alan L. (1974), "Máquinas de Turing y los espectros de fórmulas de primer orden", J. Symb. Log. , 39 (1): 139–150, doi :10.2307/2272354, JSTOR 2272354, Zbl 0288.02021
^ C. Papadimitriou y M. Yannakakis , Una nota sobre representaciones sucintas de gráficos , Información y control, vol. 71, núm. 3, diciembre de 1986, págs. 181-185, doi :10.1016/S0019-9958(86)80009-2
^ C. Papadimitriou. Computational Complexity Addison-Wesley, 1994. ISBN 0-201-53082-1 . Sección 20.1, pág. 492.

Zoológico de la complejidad : NEXP, Zoológico de la complejidad : coNEXP
Arora, Sanjeev ; Barak, Boaz (2009), Complejidad computacional: un enfoque moderno, Cambridge , pág. 57, ISBN 978-0-521-42426-4