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

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?

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 $\Sigma^*$ .

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 ?$NEXP$$NP$$2^n$$2^n$

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.$n$$n$$n$$NP$

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

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

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 $NEXPTIME$$EXPTIME$$NP$$NEXPSPACE$$EXPSPACE$(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

Un ejemplo simple es la función de tetración , que ni siquiera está en ELEMENTARY . Podrías usar alguna versión de decisión de eso.

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))$

.$\operatorname{NTIME}(f(n)) \subsetneq \operatorname{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 .

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.