Existen toneladas de problemas NP-completos y fuentes que los recopilan, por ejemplo, vea el libro de Garey y Johnson. Me interesaría ver una lista de problemas NEXP-complete también. ¿Hay uno disponible? Como supongo que no hay, abro esta pregunta (¿se supone que es una wiki comunitaria? No sé sobre esto).
Idealmente, la lista debería cubrir los diferentes "tipos" de problemas NEXP-complete, tal vez con alguna redundancia saludable para obtener una visión general, pero sin repetirse demasiado. Por ejemplo, es bueno tener dos o tres versiones sucintas diferentes del mismo problema de NP completo como ejemplos, si las codificaciones sucintas tienen formas ligeramente diferentes. No una docena Una manera limpia de agregar la redundancia es agregando cláusulas del formulario "También NEXP-complete si BLAH". Las cláusulas del formulario "Permanece NEXP-complete si el gráfico de entrada tiene grado como máximo BLAH" también son bienvenidas.
Finalmente, déjame agregar una preferencia personal. Estoy sobre todo interesado en problemas completos de sabor "algebraico", si hay alguno. Por ejemplo, mi problema favorito de # P-complete es el permanente por su sabor algebraico. Espero que la igualdad NEXP = MIP también pueda proporcionar un buen problema algebraico de NEXP completo que no conozco.
Respuestas:
Para algunos problemas NP-completos, hay una variante SUCCINCT que es NEXP-complete.
Un ejemplo es SUCCINCT HAMILTON PATH:
Del mismo modo, hay SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.
Referencia
fuente
Ver http://arxiv.org/abs/0905.2419 por Gottesman e Irani. Este es un buen ejemplo. Esencialmente, todos estamos acostumbrados a la idea de que la satisfacción de restricciones puede ser un problema NP-completo (dependiendo de la geometría, etc.) Sin embargo, consideran una situación en la que todas las restricciones se dan de antemano y lo único que se le permite variar es qué tan grande es el sistema. Sin embargo, esto sigue siendo difícil si codifica el problema en el tamaño del sistema. Es decir, el problema se especifica dando una cadena de N bits, dando el tamaño del sistema de 0 a 2 ^ N-1. Entonces, el tamaño del sistema es exponencialmente mayor que el tamaño de entrada. Muestran que esto es NEXP-complete (y que el análogo cuántico es QMA_EXP-complete).
fuente
Permítanme comenzar con el canónico:
Dada una máquina de Turing no determinista y un número entero n escrito en binario, ¿hay una ruta de cálculo de M que acepte la cadena vacía en la mayoría de los n pasos?M n M n
También NEXP-complete si está escrito en unario y pedimos como máximo 2 n pasos.n 2n
fuente
Desigualdad de expresiones regulares sobre (unión), ⋅ (concatenación) y∪ ⋅ (cuadratura)2 : Dadas dos expresiones regulares, ¿representan conjuntos diferentes?
Una expresión regular es
Estas expresiones representan los conjuntos
respectivamente.
Tenga en cuenta que si permitimos que la estrella de Kleene (cero o más copias de una expresión) sea el cuarto operador (además de la unión, la concatenación y la cuadratura), entonces el problema de reconocer si dos expresiones regulares representan idiomas diferentes se convierte en EXPSPACE-complete .
LJ Stockmeyer, AR Meyer, " Problemas verbales que requieren tiempo exponencial ", 5º STOC, 1973.
fuente
SCHÖNFINKEL – BERNAYS SAT
Referencia
fuente