Por eso, uno de los NP-Completos, problema que se ha tenido un polinomio solución, a continuación, cada uno de ellos tiene?

Question

Cada NP problema es diferente, si uno (incluso el más difícil) NP problema podría ser resuelto en el polinomio de tiempo, supongo que algo relacionado con NP problemas que podría reducirse a esta también se podría resolverse en el polinomio de tiempo. Pero, ¿por qué? ¿Significa eso que todos los otros problemas NP puede ser reducido a uno?

Algunos ejemplos podrían ser muy útiles.

Answer 1

NP integridad significa exactamente que "todos los demás problemas NP podría ser reducido [en el polinomio de tiempo] para el uno", así que sí, si una sola NP-completos problema tiene un polinomio solución de tiempo, entonces todos los problemas NP hacer. Véase la definición formal.

Tenga en cuenta que no es obvio que NP-completos, existen problemas en el primer lugar! E. g. tal vez para cada NP problema, no puedo encontrar un NP-problema B, que es "exponencialmente más difícil" que Un en el sentido de que no hay polytime-reducción de la B a la A. resulta Que este no es el caso, pero este se lleva la prueba. Algunos ejemplos de NP-completo los problemas incluyen:

• Determinar si una fórmula proposicional es válido.

• Determinar si un grafo tiene un camino Hamiltoniano.

• Determinar si una gráfica puede ser $k$-color.

Y hay muchos otros; ver esta lista.

Answer 2

Porque Si uno "NP-completo" problema puede ser resuelto sin proporcionar una solución general para toda la clase de tipo NP-completo los problemas, entonces el problema no era un NP-completo el problema, para empezar - por definición.

Answer 3

Cuando la solución de problemas en esta clase, el mismo reto surge; que cada posible solución para el primer paso o opción requiere una relación de recurrencia para la exploración de todas las otras opciones con el fin de evaluar la opción hojas que los dos estrategias; ya sea, para conseguir un equipo grande, o hacer un parcial de exploración de las opciones. Para muchos np* problemas, como el enrutamiento de las placas de circuito, o jugando al ajedrez, un parcial de exploración es suficiente. El propósito de ciertos np* problemas es exactamente para asegurarse de que un parcial de exploración es práctico - es decir, crytography / cryptocurrency / certificados, etc... Mientras que ha habido fallas en los últimos algoritmos que permiten parcial de exploración, hoy en día, la mayoría de los cripto sólo puede ser resuelto con abrumadora de alimentación del ordenador. Así que para responder a la pregunta, precisamente, uno puede ofrecer aproximaciones útiles para algunos np problemas sin resolverlos, o uno puede resolver pequeñas versiones de np problemas de búsqueda exhaustiva, pero el santo grial sigue siendo solucionar cualquier problema en np menos que la p de tiempo.