Definitii formale
P: Clasa problemelor rezolvabile in timp polinomial de o masina Turing determinista. Un algoritm O(n^k) pentru o constanta k.
NP: Clasa problemelor verificabile in timp polinomial. O solutie poate fi verificata in O(n^k). NP NU inseamna "non-polinomial" — ci "non-deterministic polinomial".
NP-completitudinea
O problema e NP-completa daca:
- E in NP
- Orice problema din NP se poate reduce la ea in timp polinomial
Teorema Cook-Levin (1971)
SAT (problema satisfiabilitatii unei formule booleene) e NP-completa. Orice problema din NP poate fi redusa la SAT in timp polinomial.
Probleme NP-complete clasice
| Problema | Descriere | Reducere din | |---|---|---| | 3-SAT | Formula 3-CNF satisfiabila? | SAT | | Clique | Exista un subgraf complet de k noduri? | 3-SAT | | Vertex Cover | Exista k noduri care acopera toate muchiile? | Clique | | Hamiltonian Cycle | Exista un ciclu care viziteaza fiecare nod o data? | 3-SAT | | Traveling Salesman | Exista un drum de lungime ≤ L? | Hamiltonian Cycle | | Knapsack | Se poate incarca o valoare ≥ V cu greutate ≤ W? | Subset Sum |
Reduceri polinomiale
O reducere A ≤_p B transforma orice instanta a problemei A intr-o instanta a problemei B, pastrand raspunsul. Daca B e rezolvabila in timp polinomial, atunci si A e.
Reducerea trebuie sa fie:
- Corecta: da ↔ da
- Polinomiala: timp de transformare O(n^k)
- Computabila: poate fi calculata
Ce inseamna P = NP?
Daca P = NP: RSA si toata criptografia cu cheie publica ar cadea, planificarea optima ar deveni posibila, inteligenta artificiala ar face salturi uriase.
Daca P ≠ NP: Exista probleme care sunt inerent grele. Nu putem face compromisul: verificare rapida nu inseamna rezolvare rapida.
Majoritatea cercetatorilor cred ca P ≠ NP, dar nu exista o demonstratie.
Teorema lui Ladner
Daca P ≠ NP, atunci exista probleme care nu sunt nici in P, nici NP-complete. Acestea se numesc probleme NP-intermediare. Exemple candidate: factorizarea numerelor, izomorfismul de grafuri, logaritmul discret.