¿Es "Objeto alcanzable" realmente un problema NP-completo?

Estaba leyendo este documento donde los autores explican el Teorema 1, que establece que "Objeto alcanzable" (como se define en el documento) es NP-completo. Sin embargo, prueban la reducción solo en una dirección, es decir, desde 2P1N SAT hasta Objeto alcanzable. Esto solo prueba que el problema es NP-duro; ¿no necesitamos probar la dirección inversa (2P1N a objeto alcanzable) para probar la integridad de NP?

complexity-theory np-complete np-hard satisfiability infinito
fuente

Los autores no han demostrado que el problema radique en NP, solo han afirmado que sí (y que es fácil probarlo). Tienen probada dureza NP.

Lagarto discreto

Solo quiero que sepas que el símbolo es \in, no \epsilon.

Alice Ryhl el

Respuestas:

Un problema $P$ NP-complete si:

$P$ es NP-hard y
$P \in \textbf{NP}$ .

Los autores dan una prueba del artículo número 1. El artículo número 2 es probablemente aparente (y debe ser claro para la audiencia del artículo). Para la prueba del número de artículo 1, solo necesita una reducción (múltiple) de algún problema de NP completo (por ejemplo, SAT) a $P$ ; no hay necesidad de construir una reducción en la dirección opuesta.

dkaeae
fuente

En caso de que alguien todavía esté confundido, 2 es trivial porque estar en NP significa que puede verificar rápidamente (tiempo polinómico) una solución al problema. Aquí, se puede verificar una solución simplemente realizando los intercambios como se indica en la solución y verificando que se alcanza el objeto deseado.

Steven Waterman el

@StevenLowes Lo único que aún tendría que verificar es que la cantidad de intercambios necesarios es polinómica. Esto tampoco es tan difícil de ver, como explico en mi respuesta.

Lagarto discreto

Había leído mal el documento y asumí que no era posible que una secuencia requiriera más de N intercambios - tienes razón :)

Steven Waterman

@StevenLowes: Bueno, también debería ser (expresable como) un problema de decisión. Hay problemas NP difíciles que no son problemas de decisión en absoluto, que obviamente no van a estar en NP, no importa cuán fáciles sean de "verificar".

Kevin

Los autores afirman que es fácil demostrar que el problema radica en NP. Para probar esta afirmación, tome una secuencia de intercambios que conduzca a un estado como testigo de que el estado es accesible. Dada tal secuencia de tamaño polinomial, podemos verificar en tiempo polinomial que el estado es realmente accesible realizando los intercambios.

Lo que queda por demostrar es que hay una secuencia de intercambios que tiene un tamaño polinómico. Tenga en cuenta que, dado que cada agente tiene preferencias estrictas y solo cambiará si puede realizar una operación que le otorgue un mejor objeto, cada agente puede intercambiar como máximo $n$ veces. Como hay a lo sumo $n$ agentes, cada secuencia de intercambios tiene como máximo $n^2$ permutas.

Creo que si hubiera preferencias no estrictas, podría ser posible que algunos elementos tengan que moverse a través de ciclos largos para alcanzar ciertos estados, y que en particular existen estados donde todas las secuencias de intercambios tienen un tamaño exponencial. Sin embargo, no puedo pensar en un ejemplo inmediato de tal problema. Por lo menos, ya no es 'fácil' mostrar que el problema con las preferencias no estrictas está en NP.

Lagarto discreto
fuente