NEXP-problemas completos

31

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.

slimton
fuente
2
Wiki de la comunidad!
Dave Clarke
¿Cómo se convierte en una wiki comunitaria?
Slimton
Marque la publicación para la atención del moderador y pídales que la hagan en sentido horario.
Kaveh
55
¿Por qué NEXP? es decir, ¿por qué no otra clase?
Suresh Venkat
1
Tenga en cuenta que la clase NEXP a veces también se conoce como NEXPTIME. Esto podría revelar resultados adicionales al usar motores de búsqueda.
Hermann Gruber el

Respuestas:

26

Para algunos problemas NP-completos, hay una variante SUCCINCT que es NEXP-complete.

Un ejemplo es SUCCINCT HAMILTON PATH:

  • Un circuito booleano con 2 n entradas y una salida representa un gráfico en 2 n vértices. Para determinar si hay un borde entre los vértices i y j , codifique i y j en n bits cada uno, y alimente su concatenación al circuito: hay un borde entre estos vértices si la salida del circuito es verdadera. Dado tal circuito, ¿hay un camino de Hamilton en el gráfico representado por el circuito?

Del mismo modo, hay SUCCINCT 3SAT, SUCCINCT KNAPSACK, etc.

Referencia

  • Hana Galperin y Avi Wigderson (1983), "Representaciones sucintas de gráficos", Information and Control 56: 3, pp. 183–198.
Gareth Rees
fuente
17

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

hastings mate
fuente
15

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?MnMn

También NEXP-complete si está escrito en unario y pedimos como máximo 2 n pasos.n2n

Slimton
fuente
15

Desigualdad de expresiones regulares sobre (unión), (concatenación) y (cuadratura)2: Dadas dos expresiones regulares, ¿representan conjuntos diferentes?

Una expresión regular es

  • ,0
  • ,1
  • ,ef
  • , oef
  • .e2

Estas expresiones representan los conjuntos

  • ,L(0)={0}
  • ,L(1)={1}
  • ,L(ef)=L(e)L(f)
  • , yL(ef)={abaL(e),bL(f)}
  • ,L(e2)=L(ee)

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.

Sadeq Dousti
fuente
14

SCHÖNFINKEL – BERNAYS SAT

  • Una fórmula en lógica de primer orden pertenece a la clase de fórmulas Schönfinkel-Bernays si puede expresarse en la forma (con que no contiene cuantificadores ni símbolos de función). Dada una fórmula de Schönfinkel-Bernays, ¿tiene un modelo?x1x2y1y2φφ

Referencia

Gareth Rees
fuente
¿El inverso (insatisfacción) coNEXP-complete?
gigabytes
Siempre pensé que una fórmula lógica de primer orden φ sin cuantificadores es una fórmula booleana. ¿No lo es? Pero para una fórmula booleana φ sería Σ ^ P_2 completo. ¿Pueden las variables en una fórmula de Schönfinkel-Bernay tener otros valores además de verdadero y falso?
BeniBela
@BeniBela: Estas son fórmulas de lógica de primer orden, por lo que puede contener símbolos de relación (cuyo significado necesita ser especificado por el modelo). Ver la referencia. Si el modelo está restringido a dos elementos, tenemos BINARY SCHÖNFINKEL – BERNAYS SAT, que sigue siendo NEXP-complete . φ
Gareth Rees