Teorema lui Cook-Levin

În teoria complexității algoritmice , teorema Cook-Levin , dovedită de Stephen Cook în lucrarea sa „The Complexity of Theorem Proving Procedures” ^[1] din 1971 , afirmă că problema satisfacției booleene este NP-completă . Matematicianul sovietic Leonid Levin a ajuns primul la dovada teoremei ^[2] , dar articolul cu dovada a fost tradus în engleză la ani după publicarea „Complexity of Theorem Proof Procedures”. Prin urmare, această teoremă este, de asemenea, cunoscută sub numele de teorema Cook-Levin, deoarece ambii matematicieni au ajuns independent la dovada teoremei.

Definiții

O problemă de decizie aparține NP dacă o mașină Turing nedeterministă poate fi calculată în soluție de timp polinomial.

O problemă de decizie este NP-completă dacă aparține NP și dacă fiecare problemă aparținând NP poate fi redusă la aceasta în timp polinomial .

Un exemplu al problemei de satisfacție booleană este o expresie booleană care combină variabilele booleene utilizând operatori booleni. O expresie este satisfăcătoare dacă există cel puțin o atribuire de valori de adevăr variabilelor astfel încât expresia să fie adevărată.

Demonstrație

Se arată că funcționarea unei mașini Turing poate fi simulată prin intermediul formulelor booleene în formă conjunctivă normală . Intuitiv, operațiunile unui computer binar (care este echivalentul Full Turing sau echivalentul lui Turing ) pot fi văzute ca formule booleene în formă normală conjunctivă (acest lucru se datorează arhitecturii computerelor ). Este demonstrat în mod trivial că orice formulă booleană poate fi transformată în timp polinomial într-o formulă booleană echivalentă în formă normală conjunctivă. Orice problemă care poate fi rezolvată de o mașină Turing poate fi transformată într-o formulă booleană și, prin urmare, problema de satisfacție booleană este NP-completă.

SAT aparține NP

SAT aparține NP, deoarece există o mașină Turing nedeterministă care poate decide toate problemele din SAT.

Această mașină face toate atribuțiile posibile cu formula booleană într-un mod nedeterminist, dacă cel puțin una dintre sarcini îndeplinește formula booleană, mașina acceptă.

Fiecare limbă din NP este reductibilă la SAT în timp polinomial

Iată dovada găsită în cartea lui Michael Sipser.

Folosim un tabel pentru a codifica toate stările unei ramuri a calculului unei mașini nedeterministe. Deci, alfabetul simbolurilor care apar în tabel este:

$C=Q\cup \Gamma \cup \{\#\}$ ${\ displaystyle C = Q \ cup \ Gamma \ cup \ {\ # \}}$ $C = Q \ cup \ Gamma \ cup \ {\ # \}$

Deoarece fiecare ramură a calculului poate avea cel mult timp polinomial, știm că stările posibile din această ramură sunt cel mult n ^k configurații. Prin urmare, este posibil să se creeze un tabel cu n ^k rânduri și n ^k coloane, dintre care fiecare rând reprezintă o configurație a ramurii de calcul.

Fiecare rând al acestui tabel conține conținutul panglicii mașinii Turing și starea curentă, plasate în fața simbolului către care este îndreptat în prezent mașina. De asemenea, simbolul # reprezintă începutul și sfârșitul fiecărui șir, iar simbolul _ reprezintă o celulă goală. De exemplu, o configurare inițială va conține simbolurile:

#, q ₀ , w ₀ , w ₁ , ... , w _n , _ , ... , _ , #

Și dacă capul ar merge înainte, am avea șirul:

#, w ₀ , q ₀ , w ₁ , ... , w _n , _ , ... , _ , #

Puteți crea un set de formule booleene care îndeplinesc anumite condiții în acest tabel:

un singur simbol este asociat cu fiecare celulă;
primul rând al tabelului reprezintă configurația inițială;
fiecare tranziție de la o linie la următoarea este validă;
cel puțin un rând al tabelului reprezintă un statut de acceptare.

Formula finală va fi conjuncția acestor patru formule:

$\phi =\phi _{cell}\land \phi _{start}\land \phi _{move}\land \phi _{accept}$ ${\ displaystyle \ phi = \ phi _ {cell} \ land \ phi _ {start} \ land \ phi _ {move} \ land \ phi _ {accept}}$ ${\ displaystyle \ phi = \ phi _ {cell} \ land \ phi _ {start} \ land \ phi _ {move} \ land \ phi _ {accept}}$

Acestea fiind spuse, trebuie demonstrate două lucruri:

este de fapt posibil să se genereze o formulă booleană de lungime polinomială din conjuncția formulelor de mai sus;
o atribuire a unei astfel de formule reprezintă o ramură de calcul pe care o acceptați

Fiecare celulă este asociată cu un singur simbol

Introducem variabilele booleene $x_{i,j,s}$ ${\ displaystyle x_ {i, j, s}}$ $x _ {{i, j, s}}$ care au valoare „adevărat” dacă celula din rândul i și coloana j conține simbolul s, „fals” în caz contrar.

Formula care verifică faptul că un singur simbol este asociat cu fiecare celulă este:

$\phi _{cell}=\bigwedge _{1\leq i,j\leq n^{k}}\left[\left(\bigvee _{s\in C}x_{i,j,s}\right)\land \left(\bigwedge _{s,t\in C;s\neq t}({\overline {x_{i,j,s}}}\lor {\overline {x_{i,j,t}}})\right)\right]$ ${\ displaystyle \ phi _ {cell} = \ bigwedge _ {1 \ leq i, j \ leq n ^ {k}} \ left [\ left (\ bigvee _ {s \ in C} x_ {i, j, s } \ right) \ land \ left (\ bigwedge _ {s, t \ in C; s \ neq t} ({\ overline {x_ {i, j, s}}} \ lor {\ overline {x_ {i, j, t}}}) \ right) \ right]}$ ${\ displaystyle \ phi _ {cell} = \ bigwedge _ {1 \ leq i, j \ leq n ^ {k}} \ left [\ left (\ bigvee _ {s \ in C} x_ {i, j, s } \ right) \ land \ left (\ bigwedge _ {s, t \ in C; s \ neq t} ({\ overline {x_ {i, j, s}}} \ lor {\ overline {x_ {i, j, t}}}) \ right) \ right]}$

Formula ne spune că pentru fiecare celulă, corespunzătoare rândului i și coloanei j, trebuie să verificăm două lucruri:

există cel puțin un simbol în celulă;
în nici o celulă nu există mai multe simboluri.

Aceasta este în mare parte o verificare sintactică a conținutului tabelului. În această formulă, nu se verifică sensul real al simbolurilor prezente.

Primul rând al tabelului reprezintă configurația inițială

Formula care verifică acest lucru este:

$\phi _{start}=x_{1,1,\#}\land x_{1,2,q_{0}}\land x_{1,3,w_{1}}\land x_{1,4,w_{2}}\land \ldots \land x_{1,n+2,w_{n}}\land x_{1,n+3,\_}\land \ldots \land x_{1,n^{k}-1,\_}\land x_{1,n^{k},\#}$ ${\ displaystyle \ phi _ {start} = x_ {1,1, \ #} \ land x_ {1,2, q_ {0}} \ land x_ {1,3, w_ {1}} \ land x_ {1 , 4, w_ {2}} \ land \ ldots \ land x_ {1, n + 2, w_ {n}} \ land x_ {1, n + 3, \ _} \ land \ ldots \ land x_ {1, n ^ {k} -1, \ _} \ land x_ {1, n ^ {k}, \ #}}$ ${\ displaystyle \ phi _ {start} = x_ {1,1, \ #} \ land x_ {1,2, q_ {0}} \ land x_ {1,3, w_ {1}} \ land x_ {1 , 4, w_ {2}} \ land \ ldots \ land x_ {1, n + 2, w_ {n}} \ land x_ {1, n + 3, \ _} \ land \ ldots \ land x_ {1, n ^ {k} -1, \ _} \ land x_ {1, n ^ {k}, \ #}}$

Orice tranziție de la o linie la următoarea este validă

Aceasta este cea mai dificilă condiție de verificat vreodată. Din acest motiv va fi furnizată o schiță demonstrativă.

Este posibil să se verifice corectitudinea rândurilor analizând doar „ferestrele” din două rânduri și trei coloane. Dintre fiecare dintre aceste ferestre puteți afla dacă este corect sau greșit uitându-vă la funcția de tranziție a mașinii Turing care este simulată și la comenzile formale.

O fereastră cu două rânduri și trei coloane poate fi incorectă din următoarele motive:

un simbol care se schimbă de la un rând la altul fără ca capul să arate spre celula în care este situat simbolul;
un rând conține două stări ale mașinii Turing;
simbolurile scrise și deplasările la stânga sau la dreapta nu fac parte din funcția de tranziție a mașinii Turing.

Acesta este:

$\phi _{move}=\bigwedge _{1\leq i<n^{k},1<j<n^{k}}({\text{la finestra (i, j) è lecita}})$ ${\ displaystyle \ phi _ {move} = \ bigwedge _ {1 \ leq i <n ^ {k}, 1 <j <n ^ {k}} ({\ text {window (i, j) is legal}} )}}$ ${\ displaystyle \ phi _ {move} = \ bigwedge _ {1 \ leq i <n ^ {k}, 1 <j <n ^ {k}} ({\ text {window (i, j) is legal}} )}}$

Fereastra (i, j) este fereastra cu două rânduri și trei coloane care are celula centrală superioară în poziție (i, j).

Cel puțin un rând din tabel reprezintă un statut de acceptare

Este vorba de a verifica dacă cel puțin o celulă din tabel conține un statut de acceptare.

$\phi _{accept}=\bigvee _{1\leq i,j\leq n^{k}}x_{i,j,q_{accept}}$ ${\ displaystyle \ phi _ {accept} = \ bigvee _ {1 \ leq i, j \ leq n ^ {k}} x_ {i, j, q_ {accept}}}$ $\ phi _ {{accept}} = \ bigvee _ {{1 \ leq i, j \ leq n ^ {k}}} x _ {{i, j, q _ {{accept}}}}$

Am spus că tabelul reprezintă o ramură a calculului unei mașini Turing nedeterministe, dar trebuie să ne asigurăm că este o ramură a calculului care se termină cu acceptarea.

Urmări

Odată ce am arătat că fiecare problemă aparținând NP poate fi redusă în timp polinomial la o instanță a problemei de satisfacție booleană , deducem că dacă această problemă ar putea fi rezolvată în timp polinomial de o mașină determinantă de Turing , toate problemele din NP ar putea fi rezolvate în timp polinomial și, prin urmare, clasa de complexitate NP ar fi egală cu clasa de complexitate P.

Notă

^ Stephen Cook, Complexitatea procedurilor de dovedire a teoremelor , în STOC '71 Proceedings of the third anual ACM symposium on Theory of computing , New York, ACM, 1971, pp. 151-158, DOI : 10.1145 / 800157.805047 .
^ Leonid Levin, Universal search problems (în rusă : Универсальные задачи перебора ^?, Universal'nye perebornye zadachi) în Problems of Information Transmission (în rusă : Проблемы передачи информации ^? ), Informatică ? 9, nr. 3, 1973, pp. 115-116. (pdf)

Bibliografie

( EN ) Sanjeev Arora, Bazra Barak, Complexitatea calculațională : o abordare modernă , 2009, Cambridge University Press, ISBN 978-0-521-42426-4 .
Michael Sipser, Introducere în teoria calculelor , ediția a treia, Cengage Learning, 2013, ISBN 978-1-133-18779-0 .

Alte proiecte

Wikimedia Commons conține imagini sau alte fișiere din teorema lui Cook

Portalul de matematică : accesați intrările Wikipedia care se ocupă de matematică

[1] Stephen Cook, Complexitatea procedurilor de dovedire a teoremelor , în STOC '71 Proceedings of the third anual ACM symposium on Theory of computing , New York, ACM, 1971, pp. 151-158, DOI : 10.1145 / 800157.805047 .

[2] Leonid Levin, Universal search problems (în rusă : Универсальные задачи перебора ^?, Universal'nye perebornye zadachi) în Problems of Information Transmission (în rusă : Проблемы передачи информации ^? ), Informatică ? 9, nr. 3, 1973, pp. 115-116. (pdf)

[1]

[2]