¿"Segunda X es NP-completa" implica "X es NP-completa"?

El problema de la "Segunda " es el problema de decidir la existencia de otra solución diferente de alguna solución dada para la instancia del problema. $X$

Para algunos problemas de -completo, la segunda versión de la solución es -completa (decidir la existencia de otra solución para el problema parcial de finalización del cuadrado latino) mientras que para otros es trivial (Segundo NAE SAT) o no puede ser completo (Segundo ciclo hamiltoniano en gráficos cúbicos) bajo una conjetura de complejidad ampliamente creída. Estoy interesado en la dirección opuesta. $NP$ $NP$ $NP$

Suponemos una naturales problema donde hay naturales verificador eficiente que verifica natural interesante relación donde es una instancia de entrada y es un corto testimonio de miembros de en . Todos los testigos son indistinguibles para el verificador. La validez de los testigos debe decidirse ejecutando el verificador natural y no tiene ningún conocimiento de ningún testigo correcto (ambos ejemplos en los comentarios son soluciones por definición). $NP$ $X$ $(x, c)$ $x$ $c$ $x$ $X$

¿"Segunda es NP-completa" implica " es NP-completa" para todos los problemas "naturales" ? $X$ $X$ $X$

En otras palabras, ¿hay algún problema "natural" donde esta implicación falla? $X$ . O equivalente,

¿Existe algún problema "natural" en y no se sabe que es completo pero su segundo problema es -completo? $X$ $NP$ $NP$ $X$ $NP$

$X$ $NP$ $X$

$X$

$NP$ $NP$ $NP$

cc.complexity-theory unique-solution Mohammad Al-Turkistany
fuente

Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .

Bjørn Kjos-Hanssen

Su EDIT 3 y EDIT 1 no parecen alinearse. Si desea que este sea un resultado general, útil para simplificar las pruebas de integridad de NP, no puede decir que solo quiere contraejemplos "no inventados". Además, sería útil tener una definición de "natural / interesante", que no se basara en una opinión personal.

Chris Jefferson

Respuestas:

No,

Considere el problema "Encuentre un subconjunto de un conjunto de enteros S que sume a 0".

Este problema es trivial, ya que uno puede devolver el conjunto vacío.

Sin embargo, encontrar una segunda solución después de devolver el conjunto vacío es el conocido problema de suma de subconjuntos, que se sabe que es NP completo.

Chris Jefferson
fuente

A menos que pueda definir un problema "antinatural", esto no importa. Las personas definen cientos de variantes de problemas como la suma de subconjuntos y SAT.

Chris Jefferson

@Mohammad: Aquí hay otro contraejemplo; Te dejo decidir si es natural o no: un juego de bimatrix siempre tiene al menos un equilibrio de Nash y es muy difícil decidir si un juego de bimatrix tiene más de un equilibrio de Nash [Gilboa y Zemel, GEB 1989] . La construcción toma una fórmula SAT f y produce un juego con cierto equilibrio de Nash de forma conocida que siempre existe, de modo que el juego tiene un segundo equilibrio si la fórmula f es satisfactoria.

Rahul Savani

f : {0, 1, 2, \dots, 2^{n} - 1} \to {0, 1}

$f : \{0,1,2,\ldots,2^n-1\} \to \{0,1\}$

f (0) = 0

$f(0) = 0$

f (2^{n} - 1) = 1

$f(2^n-1)=1$

k

$k$

f (k) = 0

$f(k) = 0$

f (k + 1) = 1

$f(k+1) = 1$

NP completo no significa que todas las instancias sean difíciles, solo algunas lo son. Hay muchas instancias triviales de suma de subconjuntos (todos los problemas que contienen 1 y - 1, por ejemplo) y muchos problemas de SAT fáciles (2 SAT, por ejemplo), pero SAT en su conjunto todavía está NP-completo.

Chris Jefferson

La respuesta debe ser un subconjunto del conjunto de enteros S. {} es un subconjunto de S ya que el conjunto vacío es un subconjunto de todos los conjuntos. {ϕ} no es un subconjunto de S, ya que S no contiene ϕ

Chris Jefferson

$ASP$ $NP$

$NP$

Mohammad Al-Turkistany
fuente

Su problema era si NP-completitud de la segunda solución implica NP-completitud. Lo que muestran es más débil, requieren integridad ASP, ya que la integridad NP no es suficiente, como se señala en los comentarios a su pregunta.

domotorp

Si alguien lee esto, esta respuesta es incorrecta. Es fácil producir un problema donde Second X es NP-complete, pero X no es NP-complete. Por ejemplo (como se discutió en los comentarios anteriores), el problema de encontrar un subconjunto de un conjunto de enteros que sume a 0 es Second X NP-complete, porque es NP-complete una vez que rechazamos la primera solución fácil del conjunto vacío .

Chris Jefferson

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Π

$\Pi$

Π_{[2]}

$\Pi_{[2]}$

Π_{[2]}

$\Pi_{[2]}$

Π

$\Pi$

Sasho Nikolov

Es un poco extraño para alguien hacer una pregunta, contestarla y luego aceptarla mientras continúa la discusión.

Chandra Chekuri

@ MohammadAl-Turkistany Mi comentario decía que su respuesta parece haber llevado la lógica al revés, y no responde a su propia pregunta. No dije nada sobre el ejemplo de Chris (que para mí se ve bien, pero no quiero entrar en ese argumento en los comentarios).

Sasho Nikolov