Cookov izrek

Iz MaFiRaWiki

Ta članek je treba še popraviti in dopolniti, kar bomo tudi storili, kakor hitro bo to mogoče. Hvala za razumevanje.

Kaj pomeni to opozorilo?

Glej pogovorno stran. Ta članek je poln napak.

Cookov izrek (prav tako znan kot Cook-Levinov izrek) pravi, da je Booleanov problem NP - poln. To pomeni, da lahko vsak problem, ki ga lahko rešimo v polinomskem času z nedeterminističnim Turingovim strojem, v polinomskem času reduciramo na problem, ali je Boolenova formula zadovoljiva.

Pomembna posledica izreka je, da če bi imeli polinomski algoritem za Booleanovo izpolnjivost, potem bi imeli algoritem, ki bi vsak problem v NP rešil v polinomskem času.


Definicije

Odločitveni problem je v NP, če je rešljiv z nedeterminističnim algoritmom v polinomskem času.

Odločitveni problem je NP-poln, če je v NP in vsak problem v NP lahko reduciramo na le ta problem v polinomskem času.

Dookaz

Booleanov problem izpolnjivosti je v NP, ker lahko nedeterministični Turingov stroj v polinomskem času ugane vrednost spremenljivk, določi vrednost izraza glede na spremenljivke in sprejme odločitev o pravilnosti.

Sedaj privzemimo, da problem v NP reši nedeterministični Turingov stroj M = (Q, Σ, s, F, δ) (kjer je Q množica stanj, Σ abeceda, sQ začetno stanje, FQ set sprejemljivih stanj, in δ : Q × ΣQ × Σ × {−1,+1} množica tranzicij) in da M sprejme ali ovrže problem v času p(n) kjer je n velikost istance in p polinomska funkcija.

Za vsak vnost I definiramo Booleanov izraz, ki je izpolnjiv, če in samo če stroj M sprejme I.

Booleanov izraz uporabi spremenljivke, ki so predstavljene v naslednji tabeli, kjer qQ, −p(n) ≤ ip(n), jΣ, in 0 ≤ kp(n):


Spremenljivke Namen Koliko?
Tijk Resnično, če trak i vsebuje simbol j na k-tem koraku računanja. O(p(n)²)
Hik Resnično, če je M's bralna/pisalna glava na celici i na k-tem koraku računanja. O(p(n)²)
Qqk Resnično, če je M v stanju q na koraku k računanja. O(p(n))



Defirniramo Booleanov izraz B kot logično konjungcijo predikatov v naslednji tabeli, za vse −p(n) ≤ ip(n) in 0 ≤ kp(n):


Predikati Pogoji Interpretacija Koliko?
Tij0 i- ta celica na traku vnosa I vsebuje simbol j. Začetna vsebina na traku. O(p(n))
Qs0   Začetno stanje M O(1)
H00   Začetna pozicija bralne/pisalne glave. O(1)
Tijk → ¬ Tij′k jj′ 1 simbol na vsako celico traku. O(p(n)²)
Tijk = Tij(k+1)Hik   Trak ostane nespremenjen, razen v primeru ko se nanj piše. O(p(n)²)
Qqk → ¬ Qq′k qq′ Samo eno stanje v danem trenutku. O(p(n))
Hik → ¬ Hi′k ii′ Samo ena pozicija glave v danem trenutku. O(p(n)²)
Disjunkcija predikatov
(HikQqkTiσk) → (H(i+d)(k+1)Qq′(k+1)Tiσ′(k+1))
(q, σ, q′, σ′, d) ∈ δ Možna tranzicija na koraku k ko je glava v poziciji i. O(p(n)²)
Disjunkcija predikatov
Qf(p(n))
fF. Mora končati v sprejemljivem času. O(1)

Če obstaja sprejemljivo stanje za M na izhodu I, potem je B izpolnjiv, če pripišemo Tijk, Hik in Qik njegove namenske interpetacije. Po drugi strani, če je B izpolnjiv, potem obstaja sprejemljivo stanje za M na izhodu I, ki sledijo korakom, ki so bili nakazani ob določitvi spremenljivk.

Kako velik je B? Imamo O(p(n)²) Booleanovih spremenljivk, ki zavzemajo O(log p(n)) prostora. Ševilo predikatov je O(p(n)²). Torej je velikost B-ja O((log p(n)) p(n)²). To je polinom v n, kar je velikost vnosov, torej je transformacija prav gotovo redukcija v polinomskem času, kar je bilo tudi zahtevano.


Posledice

Dokaz pokaže, da lahko vsak problem v NP reduciramo v polinomskem času (pravzaprav že v logaritemskem času) na problem Booleanove izpolnjivosti. To pomeni, da če bi znali Booleanov problem rešiti v polinomskem času z determinističnim Turingovim strojem, potem bi lahko vse probleme v NP rešili v polinomskem času, torej bi bil razred problemov NP enak razredu P. T

Osebna orodja