NP-completeness Flashcards
Cos’è la Problem Reduction?
Un recognition problem P1 si riduce a un recognition problem P2, se uno può risolvere ottimamente P1 usando P2 come subroutine.
Se P1 si riduce a P2 in ptime e P2 puo essere risolto in ptime da un algoritmo, questo algoritmo risolve anche P1
Cos’è la Problem Transformation?
Un rec Problem p1 si trasforma polinomialmente in un altro rec problem p2 se, per ogni istanza I1 di P1, possiamo costruire in ptime un Istanza I2 di P2 tale che I1 ha risposta ‘s1’ soltanto se I2 ha risposta si.
Definisci la classe P
Un recognition problem p1 appartiene alla classe P se qualche algoritmo ptime risolve ottimamemente P1
Classe NP
Un recognition problem p1 appartiene ad Np se esiste per ogni istanza i1 di p1 un algo polinomiale in grado di verificare che quell’istanza è una ‘yes’ istance.
I problemi della classe P appartengono ad Np?
Si, perchè ogni algoritmo che risolve un problema in P, è anche una procedure che verifica la correttezza della risposta ‘si’ in ptime
Classe Np-complete
Un rec problem P1 è Np-completo se :
1) P1 appartiene a Np
2) Tutti gli altri problemi in NP si trasformano polinomialmente in P1
Classe Np-Hard
P1 non appartiene ad Np e tutti i problemi in NP si trasformano in p1