Articles

GeeksforGeeks

by admin

Prérequis: NP-Complétude

Problème NP:
L’ensemble des problèmes NP de problèmes dont les solutions sont difficiles à trouver mais faciles à vérifier et sont résolues par une Machine Non déterministe en temps polynomial.

Problème NP-Dur :
Un Problème X est NP-Dur s’il existe un problème NP-Complet Y, tel que Y est réductible à X en temps polynomial. Les problèmes NP-durs sont aussi durs que les problèmes NP-complets. Le problème NP-dur n’a pas besoin d’être dans la classe NP.

Problème NP-complet:

Un problème X est NP-Complet s’il existe un problème NP Y, tel que Y est réductible à X en temps polynomial. Les problèmes NP-Complets sont aussi difficiles que les problèmes NP. Un problème est NP-Complet s’il fait partie à la fois du problème NP et du problème NP-Dur. Une machine de Turing non déterministe peut résoudre un problème NP-complet en temps polynomial.

Différence entre NP-Dur et NP-Complet:

NP-dur NP-complet
Les problèmes NP-durs (disons X) peuvent être résolus si et seulement s’il existe un problème NP-complet (disons Y) qui peut être réductible en X en temps polynomial. Les problèmes NP-Complets peuvent être résolus par un algorithme / machine de Turing annon-déterministe en temps polynomial.
Pour résoudre ce problème, il n’est pas nécessaire d’être en NP. Pour résoudre ce problème, il doit s’agir de problèmes NP et NP-durs.
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.