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, i Leonid Levin 1972. u radu Univerzalni problemi pretrage. Kuk je dobio Tjuringovu nagradu 1982. za ovaj rad.

Definicije

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.

Dokaz

Ovaj dokaz je baziran na dokazu koji su dali Geri i Džonson.

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 T_ijk, H_ik i Q_ik 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.

Posledice

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.

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.