Si se sabe que un problema X (problema de decisión) es NP-Completo, y se ha demostrado que se reduce al problema Y, ¿se puede decir que el problema Y es NP-Completo?

Si se sabe que un problema X (problema de decisión) es NP-Completo, y se ha comprobado que se ha reducido al problema Y en tiempo de polinomio, ¿se puede decir que el problema Y es NP-Completo?Si se sabe que un problema X (problema de decisión) es NP-Completo, y se ha demostrado que se reduce al problema Y, ¿se puede decir que el problema Y es NP-Completo?

Mi primer pensamiento fue, no, el problema Y debe demostrarse que está en NP. Pero después de pensarlo más, si X se reduce a Y, ya se considera que NP es completo. Ahora estoy confundido ... cualquier ayuda sería apreciada.

Fuente

2010-11-02 Mr. X

Creo que la tuviste la primera vez. Si podemos reducir cualquier problema conocido a otro problema completo de NP, entonces ese problema también es NP. – Jim

del wiki: "... miles de otros problemas se han demostrado que son NP-completos por reducciones de otros problemas que previamente se demostró que son NP-completos; ..." entonces, ¿diría que "sí" es la respuesta? –

Por definición, Y es "NP-hard". Un problema NP-hard es aquel que puede usarse para resolver cualquier problema en NP, incluido el problema NP-complete. Sin embargo, un problema NP-difícil no es necesariamente en NP. – gnasher729

Argumentum por contrarium:

Si X ∈ NP y X ⇔ Y e Y ∉ NP entonces X ∉ NP.

Fuente

2010-11-02 02:51:45 msw

problema X - No está seguro
Problema Y - En NP

Para demostrar X está en NP, que demuestran que se puede seguir pasos para reducir todos los problemas de X a un problema en Y. Entonces sabe que la El problema X es al menos tan difícil como el problema Y equivalente.

Así que no, es necesario comenzar con Y y luego reducir a X.

Fuente

2010-11-02 02:55:20

SAT puede ser resuelto en una sola llamada a todos, pero eso no quiere decir que todo está en NP.

Fuente

2010-11-02 06:13:26 Charles

Sí, eso es correcto. Puede reducir su problema en tiempo polinomial a cualquier problema NP ya conocido, pero se considera una tarea muy difícil. Así que, en su lugar, elige un problema completo ya NP y lo reduce a su problema y también muestra que está en NP, entonces su problema será NP completo.

Fuente

2013-12-01 00:00:25 happs

Todavía no, se necesita un par de pasos más

Con el fin de demostrar que un problema L es NP-completo, tenemos que hacer los siguientes pasos:

Demostrar su problema L pertenece NP (que es la que da una solución se puede verificar en tiempo polinómico)
Seleccione un problema NP-completo conocida L '
Describe un algoritmo que transforma f L' en L
Pro ve que su algoritmo es correcto (formalmente: x ∈ L' si y sólo si f (x) ∈ L)
Demostrar que algo f se ejecuta en tiempo polinómico

Hasta el momento se tienen paso 2,3, 4
Aún necesita mostrar que la reducción es polinómica (paso 5)
Y que el problema pertenece a NP (paso 1), que es una solución que se puede verificar en tiempo polinomial.

Fuente

2016-09-01 00:53:02

Si se sabe que un problema X (problema de decisión) es NP-Completo, y se ha demostrado que se reduce al problema Y, ¿se puede decir que el problema Y es NP-Completo?

Respuesta

Cuestiones relacionadas