Problemas NP-Hard que no están en NP pero son decidibles

Me pregunto si hay un buen ejemplo para un problema NP-Hard fácil de entender que no sea NP-Complete y no sea indecidible.

Por ejemplo, el problema de detención es NP-Hard, no NP-Complete, pero es indecidible.

Creo que esto significa que es un problema que puede verificarse una solución, pero no en tiempo polinómico. (Por favor, corrija esta afirmación si este no es el caso).

Por la versión no determinista del teorema de la jerarquía de tiempo , tenemos , donde \ mathsf {NEXP} es la clase de problemas que se pueden resolver en tiempo exponencial no determinista. Por lo tanto, es suficiente considerar cualquier problema que sea \ mathsf {NP} -hard y en \ mathsf {NEXP} , pero no en \ mathsf {NP} . Por ejemplo, podemos considerar cualquier problema completo \ mathsf {NEXP} , como$\mathsf{NP} \subsetneq \mathsf{NEXP}$$\mathsf{NEXP}$$\mathsf{NP}$$\mathsf{NEXP}$$\mathsf{NP}$$\mathsf{NEXP}$

• 3-coloración de gráficos descritos por circuitos sucintos , o cualquier otro problema NP-completo en gráficos, donde un "circuito sucinto" es un formato para representar gráficos muy grandes en la entrada: en lugar de la representación explícita de un gráfico,  por ejemplo, por listas de adyacencia, en su lugar, proporcionamos un circuito que calcula alguna función $f: \{0,1\}^{n} \times \{0,1\}^n \to \{0,1\}$ que calcula los coeficientes de un $2^n \times 2^n$ matriz de adyacencia.

• (No) equivalencia de dos expresiones regulares, donde la estrella de Kleene se reemplaza por cuadratura (repitiendo un subpatrón exactamente dos veces, en lugar de cero o más veces), y donde preguntamos si dos de esas expresiones regulares representan diferentes conjuntos de cadenas.

Tenga en cuenta que en el último caso, si tomamos expresiones regulares como estamos acostumbrados a considerar, incluida la estrella de Kleene, el problema resultante es -complete: porque tenemos las contenciones , este sigue siendo un problema decidible que es -hard, y no en .$\mathsf{EXPSPACE}$$\mathsf{NP} \subset \mathsf{NEXP} \subseteq \mathsf{EXPSPACE}$$\mathsf{NP}$$\mathsf{NP}$

Descargo de responsabilidad: esta respuesta se basa en el supuesto de que , una hipótesis que la mayoría de los científicos creen firmemente, pero aún tenemos que demostrarlo. Esto significa que existe la posibilidad de que estos problemas se encuentren en y, por lo tanto, también en .$\mbox{PSPACE} \neq \mbox{NP}$$\mbox{NP}$$\mbox{NP}$

Yo diría que los más simples son la fórmula booleana cuantificada verdadera y la geografía generalizada , ambas -completas.$\mbox{PSPACE}$

A TQBF se le da una fórmula booleana cuantificada , pruebe si la fórmula es verdadera, es decir, fórmulas en la forma es falso, porque establecer en falso produce una declaración falsa.$\forall x \exists y \forall z . \; [(x \lor y) \land z]$$z$

La geografía generalizada es un juego divertido (ver cadena de palabras ) donde tienes una lista de cadenas (por ejemplo, nombres de ciudades) y el jugador 1 comienza diciendo un nombre, y el jugador 2 responde con un nombre que comienza en la letra con la que terminó el nombre anterior. Luego es el turno del Jugador 1, hasta que alguien se quede atascado (se recomienda que este juego se juegue como un juego de beber donde los objetos son bandas / artistas, películas, ciudades, capitales, matemáticos famosos o lo que sea que flote en su bote. El que no puede responder dentro de un tiempo razonable por supuesto debe beber). El problema formal se plantea como la pregunta "¿el jugador 1 tiene una estrategia ganadora" .