Técnicas para mostrar que el problema está en la dureza "limbo"

Dado un nuevo problema en $\mathsf{NP}$ cuya verdadera complejidad está en algún lugar entre y NP-complete, hay dos métodos que sé que podrían usarse para demostrar que resolver esto es difícil: $\mathsf{P}$

Demuestre que el problema es GI completo (GI = isomorfismo gráfico)
Muestre que el problema está en . Según los resultados conocidos, dicho resultado implica que si el problema es NP-completo, entonces el PH colapsa al segundo nivel. Por ejemplo, el famoso protocolo para Graph Nonisomorphism hace exactamente esto. $\mathsf{co-AM}$

¿Hay otros métodos (tal vez con diferentes "puntos fuertes de creencia") que se han utilizado? Para cualquier respuesta, se requiere un ejemplo de dónde realmente se ha utilizado: obviamente, hay muchas maneras en que uno podría intentar mostrar esto, pero los ejemplos hacen que el argumento sea más convincente.

cc.complexity-theory np-hardness graph-isomorphism np-intermediate Suresh Venkat
fuente

Si un problema parece lo suficientemente difícil, pero no puede probar que es NPC, una comprobación rápida es contar el número de cadenas de longitud n en el idioma: si el conjunto es escaso, es poco probable que sea NPC (de lo contrario P = NP según el teorema de Mahaney) ... así que es mejor dirigir los esfuerzos para demostrar que está en P :-) :-) Un ejemplo del blog de Fortnow & Gasarch : {(n, k): existe una forma de particionar { 1, ..., n} en la mayoría de las k cajas para que ninguna caja tenga x, y, z con x + y = z}

Marzio De Biasi

@MarzioDeBiasi me suena como una respuesta.

Sasho Nikolov

Hay dos partes para tal demostración: mostrar la dificultad de colocar el problema en BPP y mostrar la dificultad de colocar el problema en la clase NP-completa. (Recordemos que la completitud GI solo significa "está en GI y es GI-hard").

$\:$

$\;\;\;$

+1 para Ricky Demer; podríamos querer tener una lista de métodos para la primera parte.

Pteromys

Para problemas en FNP sin versiones de decisión obvias en NP, PPAD es una clase útil (y creciente) a considerar. Los problemas de PPAD completo incluyen muchos problemas para encontrar puntos fijos, por ejemplo, equilibrios de Nash. La lista de Shiva es útil: cs.princeton.edu/~kintali/ppad.html

András Salamon

Respuestas:

Demostrar que su problema está en coAM (o SZK) es de hecho una de las principales formas de aportar evidencia para el "limbo de la dureza". Pero además de eso, hay varios otros:

Demuestre que su problema está en NP ∩ coNP. (Ejemplo: Factoring).
Demuestre que su problema es solucionable en tiempo cuasipolinomial. (Ejemplos: dimensión VC, aproximación de juegos gratis).
Demuestre que su problema no es más difícil que invertir funciones unidireccionales o resolver NP en promedio. (Ejemplos: muchos problemas en criptografía).
Demuestre que su problema se reduce a (p. Ej.) Juegos únicos o expansión de conjuntos pequeños.
Demuestre que su problema está en BQP. (Ejemplo: Factoring, aunque por supuesto eso también está en NP ∩ coNP.)
Descarte grandes clases de reducciones de completitud NP. (Ejemplo: El problema de minimización de circuitos, estudiado por Kabanets y Cai.)

Estoy seguro de que hay otros que estoy olvidando.

Scott Aaronson
fuente

¡Esa es una lista excelente, Scott!

Suresh Venkat

Simplemente curioso ... ¿cuál de estas técnicas muestra que es poco probable que el problema sea solucionable en tiempo polinómico (o RP, o BPP)? No vi nada que pareciera hacer esto.

Philip White

Philip: Tienes razón, ellos no. Para aportar evidencia de que un problema NP particular no está en P, todo se reduce a (1) tratar de ponerlo en P y fallar, y / o (2) reducir otros problemas que las personas no pudieron poner en P a ese problema.

Scott Aaronson

$n$

Un ejemplo es el problema de dividir los números en cajas k (del blog de Fortnow & Gasarch, fuente original: Cyberpuzzles del Doctor Ecco ):

$\{ (n,k) \mid \text{ there exists a way to partition }$ $\{1,...,n\} \text{ into at most k boxes so that no box has } x,y,z \text{ with } x+y=z \}$

Marzio De Biasi
fuente

Aquí hay tres adiciones a la lista de Scott:

Muestra que tu problema está en pocasP. Esto significa que el número de soluciones está limitado por algún polinomio. (Ejemplo: problema con la autopista de peaje). No se sabe que el problema NP-completo esté en pocos P. (imposible a menos que pocos P = NP).
$LOGNP$ $NP[log^2n]$
$2^{n^{\epsilon}}$ $NP$ $\epsilon \gt 0$ $n\ge 0$ $2^{n^{\epsilon}}$ $n$

$coNP ⊆ NP/poly$

Mohammad Al-Turkistany
fuente

¡O incluso en UP (no solo FewP)!

Joshua Grochow