Кук-Левинова теорема

Из Википедије, слободне енциклопедије

У теорији комплексности, Кук-Левинова теорема (такође позната као Кукова теорема) тврди да је САТ проблем НП-комплетан. То јест, сваки проблем који може бити решен у полиномијалном времену помоћу недетерминистичке Тјурингове машине може бити сведен (у полиномијалном времену) на САТ проблем (одређивање да ли је буловска формула задовољива).

Важна последица ове теореме је да ако бисмо имали алгоритам који у полиномијалном времену решава САТ проблем, могли бисмо у полиномијалном времену да решимо сваки проблем из класе НП.

Теорему су независно доказали Стивен Кук 1971. у раду Комплексност процедура за доказивање теорема,[1] и Леонид Левин 1972. у раду Универзални проблеми претраге.[2] Кук је добио Тјурингову награду 1982. за овај рад.

Дефиниције[уреди]

Проблем одлучивања је у класи НП ако може бити решен недетерминистичким алгоритмом у полиномијалном времену.

Проблем одлучивања је НП-комплетан ако је у класи НП, и ако сваки проблем из класе НП може бити сведен на њега у полиномијалном времену.

Буловски проблем задовољивости се састоји из буловских израза који комбинују буловске променљиве помоћу буловских оператора. Израз је задовољив ако постоји нека додела истинитосних вредности променљивима, тако да је цео израз тачан.

Доказ[уреди]

Овај доказ је базиран на доказу који су дали Гери и Џонсон.[3]

САТ проблем је у класи НП јер недетерминистичка Тјурингова машина у полиномијалном времену може да погоди доделу истинитосних вредности променљивима, одреди вредност израза под тим условима, и прихвати решење ако је цео израз тачан.

Сад претпоставимо да је проблем у НП решен недетерминистичком Тјуринговом машином M = (Q, Σ, s, F, δ) (где је Q скуп стања, Σ азбука симбола, sQ почетно стање, FQ скуп прихватајућих стања, и δ : Q × ΣQ × Σ × {−1,+1} скуп прелаза) и да M прихвата или одбија дату инстанцу проблема у времену p(n) где је n величина проблема, а p полиномијална функција.

За сваки улаз I одређујемо буловски израз такав да је задовољив ако и само ако машина M прихвата I.

Буловски израз користи променљиве дате у следећој табели, где qQ, −p(n) ≤ ip(n), jΣ, и 0 ≤ kp(n):

Променљиве Намеравана интерпретација Колико?
Tijk Тачно ако ћелија i садржи симбол j у кораку k израчунавања. O(p(n)²)
Hik Тачно ако је глава машине M над ћелијом i у кораку k израчунавања. O(p(n)²)
Qqk Тачно ако је M у стању q у кораку k израчунавања. O(p(n))

Дефинишимо буловски израз B као конјункцију клауза из следеће табеле, за све −p(n) ≤ ip(n) and 0 ≤ kp(n):

Клаузе Услови Интерпретација Колико?
Tij0 Ћелија i улаза I садржи симбол j. Почетни садржај траке. O(p(n))
Qs0   Почетно стање M O(1)
  Почетна позиција главе. O(1)
Tijk → ¬ Tij′k jj′ Један симбол по ћелији. O(p(n)²)
Tijk = Tij(k+1)Hik   Трака остаје непромењена ако се по њој не пише. O(p(n)²)
Qqk → ¬ Qq′k qq′ Само једно стање у једном тренутку. O(p(n))
Hik → ¬ Hi′k ii′ Само један положај главе у једном тренутку. O(p(n)²)
Дисјункција клауза
(HikQqkTiσk) → (H(i+d)(k+1)Qq′(k+1)Tiσ′(k+1))
(q, σ, q′, σ′, d) ∈ δ Могући прелази у кораку израчунавања k када је глава у позицији i. O(p(n)²)
Дисјункција клауза
Qf(p(n))
fF. Мора да заврши у стању прихватања. O(1)

Ако постоји прихватајуће израчунавање за M на улазу I, тада је B задовољив, додељивањем Tijk, Hik и Qik интерпретацијама. Са друге стране, ако је B задовољиво, онда постоји прихватајуће израчунавање за M на улазу I које прати кораке наведене додељивањем променљивих.

Колико је велико B? Постоји O(p(n)²) буловских променљивих, од којих свака може да буде кодирана у простору O(log p(n)). Број клауза је O(p(n)²). Тако да је величина B једнака O((log p(n)) p(n)²). Ово је полиномијално у односу на n, величину улаза, па је трансформација сигурно полиномијална редукција, као што је и било захтевано.

Последице[уреди]

Доказ показује да се сваки НП проблем може свести у полиномијалном времену на САТ проблем. Ово значи да ако би САТ проблем могао да се реши у полиномијалном времену на детерминистичкој Тјуринговој машини, онда би сви НП проблеми могли да се реше у полиномијалном времену, и то би значило да је класа комплекности НП једнака класи комплексности П.

Значај НП-комплетности је постао јасан 1972, издавањем чувеног рада Ричарда Карпа, Сводљивост међу комбинаторним проблемима, у коме је показано да је 21 проблем из комбинаторике и теорије графова, сваки познат по својој тежини, такође НП-комплетан.[4]

Карп је показао да је сваки од ових проблема НП-комплетан свођењем неког другог (за који је раније показано да је НП-комплетан) на овај проблем. На пример, показао је да је 3-САТ проблем (проблем задовољивости за буловске изразе у конјуктивној нормалној форми са тачно три литерала или негације по клаузи) НП-комплетан, показавши како да се било који САТ проблем (у полиномијалном времену) сведе на 3-САТ. (Прво се користе Де Морганови закони да се формула преведе у конјуктивну нормалну форму, а затим се уведу нове променљиве да би се разбиле клаузе са више од три литерала, јер је (A ∨ B ∨ C ∨ D) ≡ (A ∨ B ∨ Z) ∧ (¬Z ∨ C ∨ D), а клаузе са мање од три литерала се прошире новим променљивима које су гарантовано нетачне, на пример A ≡ (A ∨ Z ∨ Z) ∧ (¬Z ∨ ¬Z ∨ ¬Z).)

Гери и Џонсон су представили више од 300 НП-комплетних проблема у својој књизи Computers and Intractability: A Guide to the Theory of NP-Completeness, а и даље се откривају нови проблеми у овој класи комплексности.[3]


Извори[уреди]

  1. ^ Cook, Stephen (1971). „The Complexity of Theorem Proving Procedures“. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151-158. 
  2. ^ Levin, Leonid (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. ^ а б Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. 
  4. ^ Karp, Richard M. (1972). „Reducibility Among Combinatorial Problems“. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. стр. 85–103. 

Литература[уреди]

  • Cook, Stephen (1971). „The Complexity of Theorem Proving Procedures“. Proceedings of the third annual ACM symposium on Theory of computing. стр. 151-158. 
  • Michael R. Garey and David S. Johnson (1979). Computers and Intractability: A Guide to the Theory of NP-Completeness. Freeman. 
  • Karp, Richard M. (1972). „Reducibility Among Combinatorial Problems“. In R. E. Miller and J. W. Thatcher (editors). Complexity of Computer Computations. New York: Plenum. стр. 85–103.