Articles

GeeksforGeeks

by admin

Prerrequisito: NP-Completitud

Problema NP:
El conjunto de problemas NP cuyas soluciones son difíciles de encontrar pero fáciles de verificar y se resuelven mediante una Máquina No Determinista en tiempo polinómico.

Problema NP-Duro:
Un problema X es NP-Duro si hay un problema NP-Completo Y, de modo que Y es reducible a X en tiempo polinómico. Los problemas NP-Duros son tan duros como los problemas NP-Completos. El problema NP-Hard no necesita estar en la clase NP.

NP-Problema completo:

Un problema X es NP-Completo si hay un problema NP Y, de modo que Y es reducible a X en tiempo polinómico. Los problemas NP-Completos son tan difíciles como los problemas NP. Un problema es NP-Completo si forma parte de un problema NP y NP-Duro. Una máquina de Turing no determinista puede resolver el problema NP-Completo en tiempo polinómico.

Diferencia entre NP-Duro y NP-Completo:

NP-duro NP-Completo
NP-Los problemas difíciles(digamos X) puede ser resuelto si y sólo si hay un NP-Completo el problema(Y) que puede ser reducible a X en el polinomio de tiempo. Los problemas NP-Completos se pueden resolver mediante un algoritmo anon-determinista / Máquina de Turing en tiempo polinómico.
Para resolver este problema, no tiene que ser en NP . Para resolver este problema, deben ser problemas NP y NP-hard.
Do not have to be a Decision problem. It is exclusively a Decision problem.
Example: Halting problem, Vertex cover problem, Circuit-satisfiability problem, etc. Example: Determine whether a graph has a Hamiltonian cycle, Determine whether a Boolean formula is satisfiable or not, etc.