NP
question: Si P = NP no se resuelve, y la reducción se aplica a un problema NP-completo conocido frente a una vis π2 a π1, ¿qué conclusión se puede extraer para π1?, context: Si un problema X está en C y es duro para C, entonces X se dice que está completo para C. Esto significa que X es el problema más difícil de resolver en C. Esto se debe a que una solución de tiempo polinomial a π1 daría una solución de tiempo polinomial a π2. De manera similar, debido a que todos los problemas de NP se pueden reducir al conjunto, encontrar un problema NP-completo que se puede resolver en tiempo polinómico significaría que P = NP.
Si P = NP no se resuelve, y la reducción se aplica a un problema NP-completo conocido frente a una vis π2 a π1, ¿qué conclusión se puede extraer para π1?
de NP se pueden reducir al conjunto, encontrar un problema NP-completo que se puede resolver en tiempo polinómico significaría que P = NP.
Si un problema X está en C y es duro para C, entonces X se dice que está completo para C. Esto significa que X es el problema más difícil de resolver en C. Esto se debe a que una solución de tiempo polinomial a π1 daría una solución de tiempo polinomial a π2. De manera similar, debido a que todos los problemas de NP se pueden reducir al conjunto, encontrar un problema NP-completo que se puede resolver en tiempo polinómico significaría que P = NP.
de <hl> NP <hl> se pueden reducir al conjunto, encontrar un problema NP-completo que se puede resolver en tiempo polinómico significaría que P = NP.
Si un problema X está en C y es duro para C, entonces X se dice que está completo para C. Esto significa que X es el problema más difícil de resolver en C. Esto se debe a que una solución de tiempo polinomial a π1 daría una solución de tiempo polinomial a π2. De manera similar, debido a que todos los problemas de <hl> NP <hl> se pueden reducir al conjunto, encontrar un problema NP-completo que se puede resolver en tiempo polinómico significaría que P = NP.
Si un problema X está en C y es duro para C, entonces X se dice que está completo para C. Esto significa que X es el problema más difícil de resolver en C. Esto se debe a que una solución de tiempo polinomial a π1 daría una solución de tiempo polinomial a π2. De manera similar, debido a que todos los problemas <hl> de NP se pueden reducir al conjunto, encontrar un problema NP-completo que se puede resolver en tiempo polinómico significaría que P = NP. <hl>