¿Son los problemas NP completos también problemas NP difíciles? ¿Por qué?

Recapitulemos la definición de NP: un problema de decisión está en NP si existe una máquina de Turing no determinista que decide el problema en tiempo polinómico .

(Si alguna de las palabras anteriores es confusa o poco clara, entonces debe revisar los conceptos básicos de las máquinas de Turing y el no determinismo).

En general, una clase de complejidad (como NP ) es una colección (o conjunto) de problemas de decisión que se pueden resolver en un determinado límite de recursos (en este caso, tiempo polinómico) en un modelo específico (en este caso, TM no determinista ) Ahora, echemos un vistazo a este conjunto NP .

Ahora, supongamos que hay un problema especial (llámelo A) con una propiedad muy especial. Cada problema B en NP es poli-tiempo reducible al problema A. Dicho en términos generales, significa que si puede resolver A en un determinado límite de tiempo (podría ser exponencial, polinomial, poli-log, super-exponencial, cualquier cosa), entonces puede usarlo (solo con tiempo extra polinómico) para decidir una instancia en B. Básicamente, cada instancia de SÍ en B se asigna a una instancia de SÍ en A y cada instancia de NO en B se asigna a una instancia de NO en A y esta asignación se puede calcular en polytime. Por lo tanto, en polytime, puede reducir cualquier instancia de B a una instancia de A y decimos que resolver B es tan difícil como resolver A. Esto tiene sentido intuitivo ya que resolver A me da una solución a B (a través del mapeo polytime). Recuerde que dijimos que B es cualquier problema en NP , por lo que el problema A es tal que cualquier problema en NP es politemporalmente reducible. Decimos que A es NP-duro .

Observe un hecho extraño sobre A arriba: ¡no necesita estar en NP ! Piénselo, solo porque pueda resolver cualquier problema en NP usando A no significa que A esté en NP . Por lo tanto, el conjunto de problemas NP-hard no necesita ser un subconjunto de NP .

Supongamos que tomo una intersección de estos dos conjuntos: NP-hard y NP . Esto me da un conjunto de problemas tales que para cada problema en este conjunto,

  1. Está en NP.
  2. Todos los problemas en NP son politemporales reducibles a este problema (es decir, estos problemas son NP-hard ).

Llamamos a este conjunto de problemas NP-complete .

Espero que esto ayude 🙂

More Interesting

Si todos los códigos de computadora son 0s y 1s, ¿cómo reconoce y entiende la computadora estos símbolos en primer lugar?

¿Hay algún algoritmo de corrector ortográfico de aprendizaje no supervisado?

¿Cómo determinan los algoritmos de creación de mercado qué tan agresivamente deberían salir de las posiciones?

¿Cuál es el algoritmo utilizado por Roposo?

¿Qué es un código de clasificación?

¿Por qué el algoritmo ikj es más rápido que el algoritmo ijk para la multiplicación de matrices?

Si arr es una matriz de enteros, ¿por qué la expresión ar ++ no es legal?

¿Cuáles son los algoritmos de coincidencia de patrones más comunes?

Cómo mejorar un algoritmo para pseudo triangular un polígono

He practicado más de 300 preguntas de algoritmos en LintCode y LeetCode. He estado desempleado durante casi 9 meses y obtuve 8 entrevistas y todas fallaron en la prueba de codificación. Todavía no puedo recibir ninguna oferta. ¿Qué tengo que hacer?

¿Qué es la estructura? ¿Cuáles son las ventajas de la estructura sobre la matriz?

¿Cuáles son las mejores prácticas para usar algoritmos de Machine Learning con Android?

Cómo calcular la correlación de cada fila en una matriz 2D con una matriz 1D de la misma longitud

¿Por qué se han desarrollado los algoritmos de ordenamiento O (n ^ 2) (como el ordenamiento por inserción y el ordenamiento por burbuja) y para qué se utilizan?

¿Cuál es la mejor manera de saber qué estrategia (codiciosa, dividir y conquistar, programación dinámica) funcionaría mejor para un problema de algoritmo en particular?