Articles

GeeksforGeeks

by admin

Prerequisito: NP-Completezza

Problema NP:
L’insieme dei problemi NP di problemi le cui soluzioni sono difficili da trovare ma facili da verificare e sono risolte da Macchine non deterministiche in tempo polinomiale.

Problema NP-Difficile:
Un problema X è NP-Difficile se c’è un problema NP-Completo Y, tale che Y è riducibile a X in tempo polinomiale. I problemi NP-Hard sono difficili quanto i problemi NP-Complete. Il problema NP-Hard non deve essere nella classe NP.

NP-Problema completo:

Un problema X è NP-Completo se c’è un problema NP Y, tale che Y è riducibile a X in tempo polinomiale. I problemi NP-Completi sono difficili quanto i problemi NP. Un problema è NP-Completo se fa parte di entrambi i problemi NP e NP-Hard. Una macchina di Turing non deterministica può risolvere il problema NP-Completo in tempo polinomiale.

Differenza tra NP-Hard e NP-Complete:

NP-hard NP-Completo
NP-Hard problemi(diciamo X), può essere risolto se e solo se c’è NP-Completo di problema(diciamo Y) che può essere riducibile in X in tempo polinomiale. I problemi NP-Completi possono essere risolti da un algoritmo / macchina di Turing annon-deterministico in tempo polinomiale.
Per risolvere questo problema, non è necessario essere in NP . Per risolvere questo problema, deve essere sia problemi NP che 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.