Es importante recordar la definición de NP-completo. Una forma común de definirlo es que es un problema de decisión si está NP completo si es NP-duro y está en NP. Entonces, todo lo que tiene que hacer es demostrar que su problema de decisión tiene un algoritmo de tiempo polinomial no determinista para ser NP completo.
NP-hard significa que el problema es al menos tan difícil como los problemas más difíciles en NP. Por lo tanto, mostrar que pertenece a NP los convierte en NP completos, ya que deben ser los problemas más difíciles en NP. Eso significa que puede haber problemas que son NP-hard pero no NP-complete.
Muchos problemas que estudiamos son NP-hard, pero no necesitan (técnicamente) NP-complete ya que no son problemas de decisión; Tales ejemplos tienden a ser problemas de optimización. La variante de decisión de un problema de optimización NP-hard será NP-complete. Esto no es cierto para todos los problemas NP-hard, es solo la estructura de los problemas de optimización NP (NPO) típicamente. Por lo general, entre los investigadores, la forma en que los investigadores estudian estos problemas hace que esta diferencia sea generalmente un punto técnico, ya que normalmente sabemos cómo resolver este tipo de problemas de optimización si tuviéramos un algoritmo de tiempo múltiple para la variante de decisión (por ejemplo, usando la búsqueda binaria).
- ¿Cuál es la complejidad temporal de T (n) = T (n / a) + T (n / b) + cn cuando 1 / a + 1 / b> 1? Por ejemplo T (18n / 20) + T (5n / 20) + n.
- Si A está positivamente relacionado con B y B está positivamente relacionado con C, ¿pueden A y C estar inversamente relacionados?
- ¿De cuántas maneras podemos dividir una cadena de 10 caracteres en más de 2 subcadenas consecutivas no vacías?
- ¿Cuáles son los algoritmos que debo aprender para comenzar a estudiar la inteligencia artificial?
- ¿Qué nivel de matemática se requiere para comprender y desarrollar algoritmos?
Ahora, para mostrar que un problema NP-difícil no está en NP, todo lo que necesita hacer es mostrar que no puede estar en NP (si lo fuera, entonces obtenemos que el problema es NP-completo). Los problemas que son problemas de NPO simplemente no encajan en el NP establecido, ya que generalmente no son problemas de decisión (es por eso que usamos el término variante de decisión ), pero que yo sepa, esto no es algo trivial. con cualquier problema dado y será específico del problema. Por ejemplo, sabemos que el problema de detención definitivamente no está en NP (ni siquiera pertenece a RE), pero es NP-hard (ver ¿Por qué es difícil detener el problema de NP?) Porque es al menos tan difícil como Todos los problemas en NP. También hay más discusión sobre otros enfoques: ¿Cómo demostrar que un problema NO es NP-Complete?
Aquí hay un poco más de discusión sobre esto: ¿Los problemas difíciles de NP que no son NP completos son más difíciles?
¡Espero que esto ayude!
