Problemas decidibles "naturales" que se sabe que no están en NP.

13

Cada vez que enseño NP-Completeness, los estudiantes preguntan "¿hay algún problema que se sepa que no pertenece a NP?"

¿Cómo responderías? Por lo general, les doy un problema indecidible como ejemplo, pero esto a menudo no resulta bien: (a) si les doy el problema de detención, piensan que es un caso tonto, y (b) si les doy ecuaciones de diofantina, no veo por qué no está en NP (puede verificar las soluciones en tiempo de polietileno ... ¡solo conéctelas! Me cuesta mucho deshabilitarlas de este enfoque).

Me gustaría darles algo como QBF como ejemplo, pero no hay una separación comprobada.

Sugerencias?

Fixee
fuente
1
debería ser esto CW? es una gran lista ...
Suresh Venkat
@Suresh, depende de tu noción de natural. Debería ser breve si restringimos a lo suficientemente "natural" a los estudiantes.
Mohammad Al-Turkistany
2
El juego de Go es PSPACE completo. El juego de la vida de Conway es indecidible (es decir, es equivalente a la máquina de Turing) ... ¿son estos el tipo de ejemplos que querías?
user834
1
Decidir si un movimiento es óptimo en un tablero de ajedrez es E X P T I M E - c o m p l e t e . norteXnortemiXPAGTyoMETROmi-Cometropaglmitmi
chazisop
2
@chazisop no se sabe si contiene adecuadamente N P . miXPAGTyoMETROminortePAG
Mark Reitblatt

Respuestas:

13

Una posibilidad es un problema que es EXPSPACE-complete. NP está trivialmente en PSPACE, que está estrictamente contenido en EXPSPACE. Un problema que es EXPSPACE-complete es decidir si una expresión regular que permite la exponenciación es todo Σ .

Suresh Venkat
fuente
¿Qué significa su notación ? L(R)=L(RRR)
Neel Krishnaswami
Se generaliza la cuadratura (tomar exactamente dos copias). Tenga en cuenta que el cierre de Kleene toma arbitrariamente muchas copias
Suresh Venkat
1
Entonces, ¿es lo mismo que ? ¿O están incluidas las repeticiones infinitas? L(R)=nNL(Rn)
Neel Krishnaswami
No creo que se incluyan repeticiones infinitas.
Suresh Venkat
Gracias, y perdón por la horrible pedantería. El uso de generalmente es claro en su contexto, pero no tenía ninguno. :)
Neel Krishnaswami
11

Dado que está haciendo hincapié en los problemas naturales, aquí hay un problema completo muy natural de que no está en N P : problema de mosaico cuadrado: dado un conjunto de mosaicos finitos, ¿mosaica un cuadrado de tamaño 2 n x 2 n ?NEXPNP2n2n

Tenga en cuenta que cuando el tamaño del cuadrado es x n ( n está codificado en unario), entonces el problema se convierte en N P -completo.nnnNP

Para la completitud del mosaico cuadrado, verifique la referencia.NEXP

[1] Christos H. Papadimitriou. Complejidad computacional. Addison-Wesley, Reading, Massachusetts, 1994

Mohammad Al-Turkistany
fuente
Fascinante. Por lo tanto, el mosaico de un cuadrado de tamaño , donde n se representa en unario, es NP completo; y el mosaico de un cuadrado de 2 n × 2 n , donde n se representa en binario, es NEXP-complete. ¿Esa es la idea? ¿Se sabe algo sobre la complejidad de poner en mosaico un cuadrado n × n donde n se representa en binario? ¿O quisiste decir que n está representado en unario incluso para la primera oración de tu respuesta? n×nn2n×2nnn×nnn
DW
Sí para tu última pregunta.
Mohammad Al-Turkistany
Mosaico cuadrado es NEXP completo cuando n se representa en binario. n×nn
Mohammad Al-Turkistany
10

Se sabe que cualquier problema completo para o 2 E X P T I M E no está en N P (según el teorema de la jerarquía de tiempo). De manera similar para N E X P S P A C E y E X P S P A C ENEXPTIMEEXPTIMENPNEXPSPACEEXPSPACE(por jerarquía espacial + simulación). A menudo puede obtener problemas "falsos" al rellenar, pero los problemas naturales completos para estas clases no parecen ser tan comunes (¡probablemente porque son increíblemente difíciles!), Pero aquí hay algunos:

EXPSPACE:
equivalencia de expresión regular con operador de exponenciación

2-EXPTIME:
Satisfabilidad para CTL * (una lógica temporal)
Satisfabilidad para ATL *
Problema de decisión para la aritmética de Presburger

Mark Reitblatt
fuente
3
La aritmética de Skolem, que es aritmética con multiplicación pero no suma, también es decidible. El hecho de que pueda decidir la teoría de primer orden de uno, pero no tanto la suma como la multiplicación, me parece un hecho bastante importante.
Neel Krishnaswami
4

Según el teorema de la jerarquía de tiempo , si es una función construible en el tiempo, yf ( n + 1 ) = o ( g ( n ) ) , entonces:g(n)f(n+1)=o(g(n))

.NTIME(f(n))NTIME(g(n))

Entonces, por ejemplo, cualquier problema NEXP-complete no está en NP. Citando de Wikipedia :

Un conjunto importante de problemas NEXPTIME-complete se relaciona con circuitos sucintos. Los circuitos sucintos son máquinas simples que se usan 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 de circuito sucinta es NEXPTIME-complete, porque la entrada es exponencialmente más pequeña. Como un ejemplo simple, encontrar una ruta hamiltoniana para un gráfico así codificado es NEXPTIME-complete.

Consulte también la sección "Problemas sucintos" en la página 492 del libro de Papadimitriou .

MS Dousti
fuente
2

Un sistema de canales es un conjunto de autómatas finitos con canales de comunicación a través de los cuales pueden enviar mensajes. Un mensaje es una letra de un alfabeto. En un sistema de canales con pérdida, los mensajes pueden descartarse: una carta enviada a través de un canal puede desaparecer. El problema de accesibilidad para los sistemas de canales con pérdida es decidible pero no recursivo primitivo.

Para un ejemplo más suave, el problema de accesibilidad para los sistemas de adición de vectores es EXPSpace difícil.

Vijay D
fuente