Depende de cómo formules el problema. Por lo general, las personas cuando discuten este problema se refieren al problema de optimización. Tenga en cuenta que los problemas NP-completos son problemas de decisión, mientras que NP-hard no tiene que ser así. Su variante de problema de decisión es NP-completa (y NP-hard como NP-complete implica que existe la reducción de poli-tiempo), mientras que su variante de problema de optimización es NP-hard (no NP-complete, no es un problema de decisión). Para elaborar (tenga en cuenta que estas no son las dos únicas formas de discutir este problema):
Variante del problema de decisión: Dado un gráfico ponderado G = (V, E), ¿hay un ciclo de longitud de hamilton como máximo k (donde longitud aquí significa la suma de los pesos a lo largo de los bordes)?
Variante del problema de optimización: dado un gráfico ponderado G = (V, E), encuentre un ciclo hamiltoniano de longitud mínima.
- ¿Por qué este bucle, usado para agregar caracteres adyacentes en un vector, produce una salida extraña?
- ¿Por qué se acepta la tesis de Church-Turing? Tengo problemas para concebir un programa para una máquina de Turing que sume dos números arbitrariamente grandes.
- ¿Cuáles son algunos compromisos fundamentales en informática?
- ¿Cuáles son algunas limitaciones de la teoría de detección de señales?
- ¿Cuáles son los departamentos de investigación más sólidos para la teoría de la computabilidad (recursividad) en el mundo en este momento?
Tenga en cuenta que si tuviera un algoritmo de poli-tiempo para el primero de los dos, puede resolver el segundo utilizando la búsqueda binaria “adivinando” el valor mínimo de k. ¡Espero que esto ayude!
