Cook-Levinova teorema
U teoriji kompleksnosti, Kuk-Levinova teorema (takođe poznata kao Kukova teorema) tvrdi da je SAT problem NP-kompletan. To jest, svaki problem koji može biti rešen u polinomijalnom vremenu pomoću nedeterminističke Tjuringove mašine može biti sveden (u polinomijalnom vremenu) na SAT problem (određivanje da li je bulovska formula zadovoljiva).
Važna posledica ove teoreme je da ako bismo imali algoritam koji u polinomijalnom vremenu rešava SAT problem, mogli bismo u polinomijalnom vremenu da rešimo svaki problem iz klase NP.
Teoremu su nezavisno dokazali Stiven Kuk 1971. u radu Kompleksnost procedura za dokazivanje teorema,[1] i Leonid Levin 1972. u radu Univerzalni problemi pretrage.[2] Kuk je dobio Tjuringovu nagradu 1982. za ovaj rad.
Problem odlučivanja je u klasi NP ako može biti rešen nedeterminističkim algoritmom u polinomijalnom vremenu.
Problem odlučivanja je NP-kompletan ako je u klasi NP, i ako svaki problem iz klase NP može biti sveden na njega u polinomijalnom vremenu.
Bulovski problem zadovoljivosti se sastoji iz bulovskih izraza koji kombinuju bulovske promenljive pomoću bulovskih operatora. Izraz je zadovoljiv ako postoji neka dodela istinitosnih vrednosti promenljivima, tako da je ceo izraz tačan.
Ovaj dokaz je baziran na dokazu koji su dali Geri i Džonson.[3]
SAT problem je u klasi NP jer nedeterministička Tjuringova mašina u polinomijalnom vremenu može da pogodi dodelu istinitosnih vrednosti promenljivima, odredi vrednost izraza pod tim uslovima, i prihvati rešenje ako je ceo izraz tačan.
Sad pretpostavimo da je problem u NP rešen nedeterminističkom Tjuringovom mašinom M = (Q, Σ, s, F, δ) (gde je Q skup stanja, Σ azbuka simbola, s ∈ Q početno stanje, F ⊆ Q skup prihvatajućih stanja, i δ : Q × Σ → Q × Σ × {−1,+1} skup prelaza) i da M prihvata ili odbija datu instancu problema u vremenu p(n) gde je n veličina problema, a p polinomijalna funkcija.
Za svaki ulaz I određujemo bulovski izraz takav da je zadovoljiv ako i samo ako mašina M prihvata I.
Bulovski izraz koristi promenljive date u sledećoj tabeli, gde q ∈ Q, −p(n) ≤ i ≤ p(n), j ∈ Σ, i 0 ≤ k ≤ p(n):
| Promenljive | Nameravana interpretacija | Koliko? |
|---|---|---|
| Tijk | Tačno ako ćelija i sadrži simbol j u koraku k izračunavanja. | O(p(n)²) |
| Hik | Tačno ako je glava mašine M nad ćelijom i u koraku k izračunavanja. | O(p(n)²) |
| Qqk | Tačno ako je M u stanju q u koraku k izračunavanja. | O(p(n)) |
Definišimo bulovski izraz B kao konjunkciju klauza iz sledeće tabele, za sve −p(n) ≤ i ≤ p(n) and 0 ≤ k ≤ p(n):
| Klauze | Uslovi | Interpretacija | Koliko? |
|---|---|---|---|
| Tij0 | Ćelija i ulaza I sadrži simbol j. | Početni sadržaj trake. | O(p(n)) |
| Qs0 | Početno stanje M | O(1) | |
| H00 | Početna pozicija glave. | O(1) | |
| Tijk → ¬ Tij′k | j ≠ j′ | Jedan simbol po ćeliji. | O(p(n)²) |
| Tijk = Tij(k+1) ∨ Hik | Traka ostaje nepromenjena ako se po njoj ne piše. | O(p(n)²) | |
| Qqk → ¬ Qq′k | q ≠ q′ | Samo jedno stanje u jednom trenutku. | O(p(n)) |
| Hik → ¬ Hi′k | i ≠ i′ | Samo jedan položaj glave u jednom trenutku. | O(p(n)²) |
| Disjunkcija klauza (Hik ∧ Qqk ∧ Tiσk) → (H(i+d)(k+1) ∧ Qq′(k+1) ∧ Tiσ′(k+1)) |
(q, σ, q′, σ′, d) ∈ δ | Mogući prelazi u koraku izračunavanja k kada je glava u poziciji i. | O(p(n)²) |
| Disjunkcija klauza Qf(p(n)) |
f ∈ F. | Mora da završi u stanju prihvatanja. | O(1) |
Ako postoji prihvatajuće izračunavanje za M na ulazu I, tada je B zadovoljiv, dodeljivanjem Tijk, Hik i Qik interpretacijama. Sa druge strane, ako je B zadovoljivo, onda postoji prihvatajuće izračunavanje za M na ulazu I koje prati korake navedene dodeljivanjem promenljivih.
Koliko je veliko B? Postoji O(p(n)²) bulovskih promenljivih, od kojih svaka može da bude kodirana u prostoru O(log p(n)). Broj klauza je O(p(n)²). Tako da je veličina B jednaka O((log p(n)) p(n)²). Ovo je polinomijalno u odnosu na n, veličinu ulaza, pa je transformacija sigurno polinomijalna redukcija, kao što je i bilo zahtevano.
Dokaz pokazuje da se svaki NP problem može svesti u polinomijalnom vremenu na SAT problem. Ovo znači da ako bi SAT problem mogao da se reši u polinomijalnom vremenu na determinističkoj Tjuringovoj mašini, onda bi svi NP problemi mogli da se reše u polinomijalnom vremenu, i to bi značilo da je klasa kompleknosti NP jednaka klasi kompleksnosti P.
Značaj NP-kompletnosti je postao jasan 1972, izdavanjem čuvenog rada Ričarda Karpa, Svodljivost među kombinatornim problemima, u kome je pokazano da je 21 problem iz kombinatorike i teorije grafova, svaki poznat po svojoj težini, takođe NP-kompletan.[4]
Karp je pokazao da je svaki od ovih problema NP-kompletan svođenjem nekog drugog (za koji je ranije pokazano da je NP-kompletan) na ovaj problem. Na primer, pokazao je da je 3-SAT problem (problem zadovoljivosti za bulovske izraze u konjuktivnoj normalnoj formi sa tačno tri literala ili negacije po klauzi) NP-kompletan, pokazavši kako da se bilo koji SAT problem (u polinomijalnom vremenu) svede na 3-SAT. (Prvo se koriste De Morganovi zakoni da se formula prevede u konjuktivnu normalnu formu, a zatim se uvedu nove promenljive da bi se razbile klauze sa više od tri literala, jer je (A ∨ B ∨ C ∨ D) ≡ (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), a klauze sa manje od tri literala se prošire novim promenljivima koje su garantovano netačne, na primer A ≡ (A ∨ Z ∨ Z) ∧ (¬Z ∨ ¬Z ∨ ¬Z).)
Geri i Džonson su predstavili više od 300 NP-kompletnih problema u svojoj knjizi Computers and Intractability: A Guide to the Theory of NP-Completeness, a i dalje se otkrivaju novi problemi u ovoj klasi kompleksnosti.[3]
- ↑ Stephen Cook (1971). „The Complexity of Theorem Proving Procedures”. Proceedings of the third annual ACM symposium on Theory of computing. str. 151–158.
- ↑ Leonid Levin (1973). „Universal'nye perebornye zadachi”. Problemy Peredachi Informatsii 9 (3): 265–266. English translation, "Universal Search Problems", in B. A. Trakhtenbrot (1984). „A Survey of Russian Approaches to Perebor (Brute-Force Searches) Algorithms”. Annals of the History of Computing 6 (4): 384-400.
- ↑ 3,0 3,1 Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman.
- ↑ Richard M. Karp (1972). „Reducibility Among Combinatorial Problems”. u: R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. str. 85–103.