Cook-Levin teoremi; C=\\{s_1,s_2,_ldots,s_l\\'' _end{array} Şimdi neye bakanımdır?
F ifadesinin ne gibi koşulları sağlaması gerektiğine
Tüm satırlar bu kurallara uygun olarak doldurulduktan sonra tablo N makinesi için herhangi bir kabul durumu içeriyorsa A tablosu kabul verir yoksa ret verir. Böylelikle A dili bu tablo aracılığıyla simule edilebilir. Böylelikle N makinesinin w’yı kabul etmesi artık tablonun qkabul durumunu içerip içermemesine indirgenmiş oldu.Şimdi sıra elde ettiğimiz tablodan SAT problemine geçmek için bir boolean formül (∅)elde etmeye geldi.F formülüne geçmeden önce kullanacağımız birkaç önemli terimi ifade edelim: Q : N makinesinin durumları kümesi Γ : N makinesinin alfabesi C = Q ∪ Γ ∪ {#} : Tablodaki değişkenler kümesi xi,j,s : ∅ formülünün değişkeni olup tablonun [i,j] gözünde s değeri varsa doğru yoksa yanlış değerini alır. :\begin{array}{l} \bigvee_{s\in C}x_{i,j,s}=x_{i,j,s_1}\scriptstyle\land x_{i,j,s_2}\scriptstyle\land\ldots\scriptstyle\land x_{i,j,s_l} \\\ C=\\{s_1,s_2,\ldots,s_l\\} \end{array} Şimdi F ifadesinin ne gibi koşulları sağlaması gerektiğine bakalım. # Tablonun her hücresinde tek bir boolean değişken olmalıdır. Bunu göstermek için şu iki şart sağlanmalıdır. ::a. Tablonun her hücresinde en az bir değişken olmalıdır. ::b. Tablonun her hücresinde en fazla bir adet değişken olmalıdır. :::\mathrm{\text{Dolayısıyla }}\emptyset_{\mathrm{\text{hücre}}}=\bigwedge_{1 \le i,\ j \le n^k} \left[\left(\bigvee_{s \in C} x_{i,j,s}\right) \scriptstyle\land \left(\bigwedge_{s,t \in C \atop s e t}\left(\overline{x_{i,j,s}} \scriptstyle\lor \overline{x_{i,j,t}}\right)\right)\right] :2. Tablonun başlangıç konfigürasyonu N makinesinin başlangıç konfigürasyonu olmalıdır. :::\emptyset_{\mathrm{\text{başlangıç}}}=x_{1,1,\\#} \scriptstyle\land x_{1,2,q_{0}} \scriptstyle\land x_{1,3,w_{1}} \scriptstyle\land x_{1,4,w_{2}} \dots \scriptstyle\land x_{1,n^k,\\#} doğrulanmalıdır. :3. Tabloda en az bir tane N makinesine ait kabul durumu (qkabul ) bulunmalıdır. ::Dolayısıyla \emptyset_{\mathrm{kabul} }=\bigvee_{1\le i,j\le n^k}\chi_{i,j,q_{\mathrm{kabul} } } doğrulanmalıdır. :4. Tablodaki konfigürasyonlar arasındaki geçiş N makinesinin kurallarına uygun olmalıdır. :::\emptyset_{\mathrm{hareket}}=\bigwedge_{1 < i \le n^k,\ 1 < j < n^k} \left((i,j)\ \mathrm{\text{penceresi geçerli penceredir}}\right) doğrulanmalıdır. ::Bir pencerenin geçerli olması ne demek onu inceleyelim. Tablonun 3×2’lik parçasına pencere diyoruz ve bu pencere geçiş fonksiyonuna uygunsa buna geçerli pencere diyoruz. Dolayısıyla problemimiz ∅ = ∅hücre ∧ ∅ başlangıç ∧ ∅ kabul ∧ ∅ hareket probleminin doğrulanmasına indirgendi. Diğer bir deyişle A dilini SAT diline indirgemiş olduk. İndirgemeyi yaptık şimdi bunun polinom zamanda olduğunu ispatlamaya geldi sıra. İndirgemenin karmaşıklığını göstermek için ∅ formülünün boyutu göstermek yeterli olacaktır. Tablonun boyutu nk ×nk olup n2k hücreye sahiptir ve bu hücrelerde l farklı değişken bulunabilir. (l∈C ). l değeri N makinesine verilen w katarından bağımsız olduğu için ∅ formülündeki değişken sayısı O(n2k) olacaktır. Dolayısıyla bu indirimin polinom zamanda yapılmış olduğu anlamına geliyor. Böylelikle SAT probleminin NP-tam olduğunu göstermiş olduk. Sonuç: Şimdi bunun bize ne katacağını ifade edelim, Farz edelim ki SAT problemine polinom zaman da bir çözüm bulunmuş olsun ("SAT ∈ P"). Bu bize şunu ifade eder SAT problemi hem NP sınıfının içinde (Cook-Levin teoreminden) hem de P sınıfının(varsayımdan) içinde ve diğer yandan her NP dili SAT problemine polinom zamanda indirgenebiliyor (Cook-Levin teoreminden) dolayısıyla bu NP sınıfı ile P sınıfın denk olduğu anlamına geliyor. Aslında Cook-Levin ikilisinin bu teorem ile amaçladıkları şey de tam olarak buydu yani P ile NP sınıfının eşitliğini iddia eden biri NP-tam sınıfından bir probleme polinom zamanda çözüm bulması iddiasını kanıtlamak için yeterli olacaktır. .Karmaşıklık teorisindendir. Matematik teoremleri.