¿Por qué es importante la clase NP-Complete en comparación con NP-hard?

19

Estoy estudiando la complejidad computacional y me preguntaba por qué los problemas NP-Complete (NPC) son una clase importante en absoluto. Me parece obvio por qué estamos interesados ​​en mostrar que un problema NP dado es NP-hard.

También entiendo la definición de NPC, y que mostrar un problema de decisión dado es NP-difícil, sabiendo que está en NP, es exactamente lo que significa NPC.

Sin embargo, lo que no entiendo es: ¿por qué este concepto es tan importante? Seguramente, si nos encontramos con cualquier algoritmo NP-duro que se extiende en el tiempo P (ya sea o no que está en NP), hemos demostrado que .NP=P

¿Por qué es tan importante este concepto?

complexity-theory np-complete Amnésico
fuente
3
Eliminé tu segunda pregunta porque está completamente separada de la primera. Sin embargo, es una muy buena pregunta y le animo a que la haga como una nueva pregunta. Para recuperar el texto, haga clic en el enlace "editado [en cualquier momento]", que le mostrará el historial de edición y le permitirá copiar y pegar el texto.
David Richerby

Respuestas:

16

Hay al menos algunas razones por las que NPC es interesante:

  • La clase NP contiene muchos problemas que son interesantes (tanto práctica como teóricamente), además, muchos de estos problemas resultan ser NP-difíciles (y por lo tanto NP-completos), pero muchos problemas fuera de NP son casi seguramente demasiado difíciles de resolver. más que un interés teórico , por lo que NPC proporciona un grupo (aproximado) de problemas que aparentemente son difíciles, pero no tanto que no podemos tratar de hacer algo con ellos.
    En otras palabras, NPC es probablemente el límite de lo que podemos esperar que sea solucionable en tiempo polinómico, parecería una exageración intentar para PSPACE = P (por ejemplo).
  • La clase es NP es estructuralmente interesante. Es el ejemplo básico de "¿obtenemos más" velocidad "computacional del no determinismo". Por lo tanto, estamos interesados ​​en si P = NP o no, y NPC es (probablemente) un componente importante para resolver eso.
  • NP-hard (como clase) es realmente demasiado grande y variado para tratarlo como una sola cosa, es todo lo que se puede reducir a partir de un problema de NP completo , incluida una gran cantidad de cosas fuera de NP, así que desde el punto de vista de En vista de tratar de desarrollar resultados y técnicas generales, no hay nada a lo que agarrarse.
Luke Mathieson
fuente
Como mi pregunta original fue editada para reflejar el título, tal vez también debería ocultar la respuesta de la segunda pregunta.
Amnésico
1
NP-hard no es "todo fuera de NP", ya que incluye (al menos) los problemas de NP completo en NP. Entiendo lo que quieres decir, pero no sé cómo decirlo sucintamente.
vonbrand
@vonbrand, sí, exageré mucho (¿tal vez una locura?). La nueva versión es precisa, pero desafortunadamente no tiene la sensación.
Luke Mathieson
9

Desde el punto de vista de alguien que escribe código para ganarse la vida, tener una buena familiaridad con la integridad de NP es importante para:

1. Reconociendo cuando estás ladrando el árbol equivocado

Los problemas NP-completos son los problemas NP-hard más fáciles y, sin embargo, por lo que podemos decir, lleva tiempo exponencial al tamaño de la entrada para resolver un problema de decisión. Entonces, como una cuestión práctica si puede demostrar que el problema que está tratando de resolver es NP-difícil (por lo general, mostrando que una solución eficiente también daría una solución eficiente a algún problema NP-completo), usted sabe que puedes dejar de buscar un algoritmo eficiente para resolverlo exactamente en general. En su lugar, puede seleccionar entre algoritmos conocidos que prometen buenas aproximaciones para problemas de optimización NP-hard y continuar con el resto de su proyecto.

2. Encontrar el árbol correcto

Debido a que las computadoras se usan a menudo para atacar problemas NP-hard, se han desarrollado solucionadores especializados que pueden resolver eficientemente algunas instancias de problemas NP-hard. Reconocer que su problema es NP-complete es el primer paso para encontrar una herramienta existente (SAT, ILP, SMT, CSP, por nombrar algunas) que podría ayudarlo a encontrar soluciones exactas en algunos casos en los que de otro modo habría tenido que conformarse con un aproximación.

Kyle Jones
fuente
-4

"Sin duda, si encontramos algún algoritmo NP-hard que se ejecute en el tiempo P (ya sea que esté en NP o no), hemos demostrado que NP = P. ¿Por qué es tan importante este concepto?"

Cada problema de NP se reduce a cualquier problema de NPC, pero no es cierto que cada problema de NP se reduzca a cualquier problema de NP-hard, por lo que probar que un algoritmo NP-hard está en P no prueba P = NP en absoluto. Sería el caso, sin embargo, para un problema de NPC, eso es precisamente lo que significa "reducir". Entonces, si encontramos un algoritmo P para un problema de NPC, habremos demostrado que P = NP.

anónimo
fuente
3
Lo siento pero esto es incorrecto. La definición de un problema es NP -Hard es que todos los problemas de NP reduce a . XXX
David Richerby