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 .
- ¿Puedes predecir la lotería con algoritmo?
- ¿Cómo se explica el algoritmo de Metropolis-Hastings en términos simples?
- ¿Qué algoritmo debo usar en este problema de geometría?
- ¿Hay algún algoritmo que compita con RegEx? ¿Hay una manera fácil de ejecutar Python RegEx en una GPU?
- ¿Cuál es la mayor complejidad de tiempo que cualquier juez en línea puede aceptar como O (10 ^ 9) o algo en términos de números?
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,
- Está en NP.
- 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 🙂
