Problemas que son decidibles pero que no pueden verificarse en tiempo polinómico

Mientras trabajaba en un proyecto algo no relacionado para Suresh, recientemente me encontré con un trabajo realizado por Page y Opper sobre sistemas componibles por el usuario y una parte de su trabajo discutió brevemente problemas que no pueden verificarse en el tiempo polinómico. No he podido encontrar mucha información sobre otros problemas que no pueden verificarse en el tiempo polinómico o un análisis de dicho problema. Me preguntaba si alguno de ustedes sabía de tales problemas y / o cómo analizarlos.

Como se indicó en los comentarios, una mejor manera de formular esta pregunta es: ¿Qué problemas son decidibles pero fuera de NP?

cc.complexity-theory complexity-classes Scott R
fuente

¿Problemas fuera de ?

N P

$\mathsf{NP}$

Hsien-Chih Chang 張顯之

Sí, específicamente aquellos que se pueden verificar, pero no en el tiempo polinómico.

Scott R

Es posible que vea estos

N E X P

$\mathsf{NEXP}$ problemas completos y proporcione reducciones de ellos. cstheory.stackexchange.com/questions/3297/…

Hsien-Chih Chang 張顯之

El problema no hamiltoniano no se puede verificar en tiempo polinómico a menos que coNP = NP.

Mohammad Al-Turkistany

@turkistany @ Hsien-Chih Chang, ¿por qué no publicar sus comentarios arriba como respuestas?

Kaveh

Respuestas:

Lo más importante a tener en cuenta desde un punto de vista teórico es que NP es en realidad una clase relativamente pequeña de todos los lenguajes decidibles. Dicho esto, muchos de los problemas interesantes en informática se encuentran dentro de NP, por lo que reciben mucha atención.

Se conjetura que . $NP \subsetneq PH \subsetneq PSPACE \subsetneq EXP \subsetneq NEXP$

Las clases PH, PSPACE y EXP contienen muchos de los problemas "interesantes" en , que es lo que supongo que estás preguntando en esta pregunta. Hasta ahora, NEXP ha recibido toda la atención porque es la única contención adecuada que podemos probar (por el teorema de la jerarquía de tiempo no determinista, como mencioné anteriormente). $R \setminus NP$ $NP \subsetneq NEXP$

Aquí hay algunos ejemplos concretos interesantes de problemas en algunas de estas otras clases:

Determinar si un jugador tiene una estrategia ganadora en ajedrez o Go (adaptado a nxn tableros) es EXP-complete.
MAJ-SAT, el problema de determinar si más de la mitad de las asignaciones a las variables en una fórmula booleana satisface esa fórmula, está en PSPACE. También está completo para la clase más pequeña PP.
EXACT-CLIQUE, el problema de determinar si la camarilla más grande en un gráfico tiene un tamaño exactamente k, está en , parte del segundo nivel de la jerarquía polinómica. $\Sigma_2^P$

Huck Bennett
fuente

Por curiosidad, ¿es la clase de problemas recursivos el significado 'estándar' para R? Eso es lo que parece indicar el Zoo, pero he visto a R como sinónimo de RP con tanta frecuencia que esa fue mi lectura instintiva cuando vi R \ NP ...

Steven Stadnicki

Creo que es una notación estándar. Encaja muy bien con "RE" y "co-RE".

Huck Bennett el

Tanto el ajedrez como el Go son típicamente EXPTIMOS completos debido a las reglas de repetición.

Geoffrey Irving

@GeoffreyIrving: Tienes razón, gracias. Fijo. No estoy seguro de lo que (por error) tenía en mente cuando escribí eso, pero hay " subproblemas

Huck Bennett

Bueno, si tuvieras un oráculo PSPACE a mano, probablemente podrías jugar bastante bien. :)

Geoffrey Irving

Extendiendo el comentario de Hsien-Chih Chang, cada problema difícil de NEXP no puede estar en NP, por lo tanto, por definición, no puede verificarse en tiempo polinómico.

Se podría usar el teorema de la jerarquía temporal no determinista para ver que NP está estrictamente contenido en NEXP. Por lo tanto, podemos estar seguros de que, dado cualquier problema difícil de NEXP, no está en NP o nos llevaría a una contradicción.

chazisop
fuente

Sin embargo, tenga en cuenta que Buhrman, Fortnow y Santhanam construyen un oráculo con respecto al cual NEXP está contenido infinitamente a menudo en NP ( dx.doi.org/10.1007/978-3-642-02927-1_18 ). En otras palabras, hay un oráculo con respecto al cual para cada problema NEXP L, hay un problema L 'en NP tal que L es igual a L' en infinitas longitudes de entrada. Entonces, aunque no se pueden verificar infinitamente muchas instancias de un problema NEXP-complete en el tiempo poli, no podemos (relativizadamente) descartar la posibilidad de que se puedan verificar infinitas instancias en el tiempo poli.

Joshua Grochow