Hispanopedia Wiki
Articulo de referencia

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 ser resueltos por una ...

Hispanopedia WikiContenido en espanolLectura gratuita

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 utilizando tiempo2norteO(1){\displaystyle 2^{n^{O(1)}}}.

En términos de NTIME ,

nortemiincógnitaPAGTIMETROmi=⋃k∈nortenorteTIMETROmi(2nortek){\displaystyle {\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 todo x e y , la máquina M funciona en tiempo2pag(|incógnita|){\displaystyle 2^{p(|x|)}}en la entrada(incógnita,y){\displaystyle (x,y)}⁠
  • Para todo x en L , existe una cadena y de longitud2q(|incógnita|){\displaystyle 2^{q(|x|)}}de tal manera queMETRO(incógnita,y)=1{\displaystyle M(x,y)=1}⁠
  • Para todo x que no está en L y todas las cadenas y de longitud2q(|incógnita|){\displaystyle 2^{q(|x|)}},​METRO(incógnita,y)=0{\displaystyle M(x,y)=0}⁠

Lo sabemos

P ⊆ NP ⊆ EXPTIME ⊆ NEXPTIME

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

NP ⊊ PRÓXIMA VEZ

Si P = NP , entonces NEXPTIME = EXPTIME ( argumento de relleno ); más precisamente, E ≠ 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 precisamente 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 suele surgir en el contexto de los sistemas de prueba interactivos , donde existen dos caracterizaciones principales. La primera es el sistema de prueba MIP , en el que tenemos dos probadores todopoderosos que se comunican con un verificador aleatorio de tiempo polinomial (pero no entre sí). Si la cadena pertenece al lenguaje, deben ser capaces de convencer al verificador de ello con alta probabilidad. Si la cadena no pertenece al lenguaje, no deben ser capaces de engañar colaborativamente al verificador para que la acepte, salvo con baja probabilidad. El hecho de que los sistemas de prueba MIP puedan resolver cualquier problema en NEXPTIME es bastante impresionante si consideramos que, cuando solo hay un probador presente, solo podemos reconocer todo PSPACE ; la capacidad del verificador para "interrogar" a los dos probadores le confiere un gran poder. Véase sistema de prueba interactivo#MIP para más detalles.

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

  • Añada aleatoriedad, la posibilidad de lanzar monedas al aire, a la máquina verificadora.
  • En lugar de simplemente entregar la supuesta prueba al verificador en una cinta, se le otorga acceso aleatorio a la misma. 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 acceder a una cadena de prueba de longitud exponencial.

Estas dos extensiones, en conjunto, amplían considerablemente la capacidad del sistema de pruebas, permitiéndole reconocer todos los lenguajes en NEXPTIME . La clase se denomina PCP (poly, poly). Además, en esta caracterización, el verificador puede limitarse a leer solo un número constante de bits, es decir, NEXPTIME = PCP (poly, 1). Consulte las pruebas verificables probabilísticamente para obtener más detalles.

NEXPTIME-completo

Un problema de decisión es NEXPTIME-completo si está en NEXPTIME y todo problema en NEXPTIME tiene una reducción de muchos a uno en tiempo polinomial. En otras palabras, existe 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 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 pueden verificarse en tiempo polinomial , según el teorema de jerarquía temporal .

Ejemplos de problemas NEXPTIME-completos

Problemas concisos

Un conjunto importante de problemas NEXPTIME -completos se relaciona con los 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 devuelven 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 logra mediante una "proyección"). [ 3 ] [ 4 ] Como un ejemplo simple, encontrar un camino hamiltoniano para un grafo codificado de esta manera es NEXPTIME -completo.

Lógica

El problema de satisfacibilidad de la lógica de primer orden con dos variables es NEXPTIME-completo. [ 5 ] El problema de satisfacibilidad de la lógica de primer orden con conteo y con dos variables es NEXPTIME-completo. [ 6 ]

Juegos

Decidir si una fórmula en fórmulas binarias cuantificadas por dependencia (DQBF, que es una versión de información imperfecta de QBF ) es verdadera es NEXPTIME-completa. [ 7 ] La información imperfecta con equipos de lógica de restricciones también es NEXPTIME-completa. [ 8 ] Resolver un proceso de decisión de Markov parcialmente observable descentralizado es NEXPTIME-completa. [ 9 ]

Véase también

Referencias

  1. ↑ Juris Hartmanis, Neil Immerman, Vivian Sewelson. Conjuntos dispersos en NP-P: EXPTIME versus NEXPTIME. Information and Control , volumen 65, número 2/3, págs. 158-181 . 1985. En la Biblioteca Digital de la ACM.
  2. ↑ 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  
  3. ↑ C. Papadimitriou y M. Yannakakis , Una nota sobre representaciones sucintas de grafos , Information and control, vol. 71, núm. 3, diciembre de 1986, págs. 181-185, doi : 10.1016/S0019-9958(86)80009-2
  4. ↑ C. Papadimitriou. Complejidad computacional. Addison-Wesley, 1994. ISBN 0-201-53082-1Sección 20.1, pág. 492.
  5. ↑ Etessami, Kousha; Vardi, Moshe Y.; Wilke, Thomas (15 de diciembre de 2002). "Lógica de primer orden con dos variables y lógica temporal unaria" . Information and Computation . 179 (2): 279–295 . doi : 10.1006/inco.2001.2953 . ISSN 0890-5401 . 
  6. ↑ Pratt-Hartmann, Ian (14 de julio de 2014). «Lógicas con conteo y equivalencia» . Actas de la Reunión Conjunta de la Vigésimo Tercera Conferencia Anual de la EACSL sobre Lógica en Ciencias de la Computación (CSL) y el Vigésimo Noveno Simposio Anual ACM/IEEE sobre Lógica en Ciencias de la Computación (LICS) . CSL-LICS '14. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1-10 . doi : 10.1145/2603088.2603117 . ISBN  978-1-4503-2886-9.
  7. ↑ Peterson, Gary L.; Reif, John H. (octubre de 1979). "Alternancia de varias personas". XX Simposio Anual sobre Fundamentos de la Informática (SFCS 1979) . págs. 348–363 . doi : 10.1109/SFCS.1979.25 . 
  8. ↑ Hearn, Robert Aubrey (2006). Juegos, rompecabezas y computación (tesis doctoral). EE. UU.: Instituto Tecnológico de Massachusetts.
  9. ↑ Bernstein, Daniel S.; Givan, Robert; Immerman, Neil; Zilberstein, Shlomo (2002). "La complejidad del control descentralizado de los procesos de decisión de Markov" . Matemáticas de la investigación operativa . 27 (4): 819– 840. ISSN 0364-765X .