Cook-Levin teoremi

SAT problemi bir NP-tam sınıfı problemidir.

Giriş

Teoremin ispatına geçmeden önce teoremin çıkış noktası üzerinde duralım. Polinom zamanda kararlaştırılan problem (P sınıfı problemleri) ile polinom zamanda doğrulanabilen problem (NP sınıfı problemleri) sınıflarının birbirine denk olup olmadığı güncel matematik ve teorik bilgisayar biliminin bir türlü çözemediği bir sorun olagelmiştir. Eğer bu sınıflar birbirine denk olduğu gösterilirse herhangi polinom zamanda doğrulanabilen bir problemin (NP sınıfı problemi) artık polinom zamanda kararlaştırılabiliyor olacağı kesin olarak söylenmiş olacaktır.

1970’lerde P ve NP sınıflarının arasındaki ilişkiye Stephen Cook ve Leonid Levin adındaki iki bilim adamı farklı bir açıdan yaklaşmışlardır; bazı NP sınıfı problemlerinin karmaşıklıklarının tek başlarına tüm NP sınıfının karmaşıklığına eşit olduğunu fark etmişler. Eğer bu tip problemlerin polinom zamanda bir çözümü bulunursa NP sınıfındaki tüm problemler polinom zamanda çözülebilir. Bu tip problemlere ileride değineceğiz ve bun tip problemlere NP-tam sınıfı problemleri diyeceğiz. Dolayısıyla Cook-Levin yaklaşımının bir sonucu olarak P sınıfıyla NP sınıfının eşitliğini iddia eden biri NP-tam bir problemi polinom zamanda çözmesi iddiasını ispatlamak için yeterli olacaktır.

SAT Problemi

SAT (Doğrulanabilirlik) probleminin ne olduğundan bahsedelim. SAT problemi verilen bir boolean ifadenin sonucunun doğru olup olmayacağıyla problemidir. Yani boolean ifadeyi doğru kılacak, boolean ifadenin değişkenlerinin bir “doğru, yanlış” kombinasyonunun oluşturup oluşturmayacağıyla ilgilenir. Dolayısıyla SAT problemi aşağıdaki gibi ifade edilebilir:

$SAT=\left\{\langle \varnothing \rangle \vert \varnothing \,{\text{dogrulanabilir boolean ifadedir}}\right\}$

Örneğin $\varnothing =\left({\bar {x}}\scriptstyle \land y\right)\scriptstyle \lor \left(x\scriptstyle \land z\right)$ gibi herhangi bir boolean ifadenin sonucunun doğru olmasını inceleyen probleme SAT problemi denir. Bu örnekte x = doğru, y = yanlış, z = doğru için problem doğrulanabilirdir.

NP-Tam Sınıfı

Bir B dili NP-tam ise şu iki şartı sağlamalıdır:

1. B dili NP sınıfındadır.
2. NP sınıfındaki her dil B diline polinom zamanda indirgenebilir.

Burada yeni bir kavramla karşılaşıyoruz; “polinom zamanda indirgemek”. Bunu fazla derine inmeden şöyle özetleyebiliriz; eğer bir problemin çözümünü bilmiyorsak ya da çözümü bulmakta çok zorlanıyorsak asıl problemimizi çözmeye yardımcı olacak yeni bir probleme indirgeriz ve çözüme yeni indirgenmiş problem aracılığıyla ulaşırız. Eğer bu indirgememiz polinom zamanda gerçekleştirilirse buna da “polinom zamanda indirgemek” adını veririz. Buna şöyle bir örnek verebiliriz: Bilmediğiniz bir yere gitmek istediğinizi farz edelim ve bu problemin sizin için zor bir problem olduğunu düşünelim. Bu durumda gideceğiniz yere ulaşmak için bir yardımcıya ihtiyacınız olacaktır. Bu yardımcılar taksiye binmek, harita elde etmek ya da bilen birine sormak bunlar arasında sayılabilir. Böylelikle bizim için zor olan problemimiz taksi ya da harita bulmak kadar basit bir probleme indirgenmiş oldu. Kısaca buna da değindikten sonra artık teoremimize dönelim.

İspat

SAT probleminin NP-tam sınıfına ait bir problem olduğunu göstermek için öncelikle SAT dilinin NP sınıfında olduğunu göstermemiz lazım.

SAT probleminin NP sınıfında olduğunu göstermenin iki farklı yolu vardır:

1. SAT problemini polinom zamanda doğrulayan bir Turing Makinesi(TM) tasarlamalıyız.
2. Ya da SAT problemini polinom zamanda kararlaştıran bir deterministik olmayan Turing Makinesi (NTM) tasarlamalıyız.

Biz burada 2. yolla bunu ispatlayalım: Deterministik olmayan N Turing Makinesi, SAT dilini polinom zamanda aşağıdaki gibi kararlaştırsın:

N: “ ∅ ’nin Boolean ifade, x₁, x₂, x₃,...., x_k’nin de bu ifadenin bir değişkeni olsun ve makine girdi olarak < ∅, x₁, x₂, x₃,...., x_k > katarını alsın.

1. Deterministik olmayacak şekilde boolean ifadedeki değişkenlere “doğru ve yanlış” değerlerini ata.
2. Elde edilen kombinasyonla boolean formülün doğru cevap üretip üretmediğini kontrol et. Eğer cevap doğruysa kabul ver. Eğer cevap yanlışsa ve tüm kombinasyonlar denenmişse ret ver, eğer cevap yanlış ve tüm kombinasyonlar denenememişse 1’e dön.

Şimdi sıra NP’deki her dilin SAT diline polinom zamanda indirgemekte. A dilini n^k zamanda kararlaştıran determinist olmayan bir N Turing Makinesi düşünelim. Aşağıda anlatacağım yöntem aracılığıyla N makinesini SAT diline indirgeyeceğiz.

453 × 337px

Bu tabloda her bir satır N makinesinin konfigürasyonunu ifade ediyor. Kolaylık olsun diye her konfigürasyonun "#" ile başlayıp "#" ile bittiğini farz edelim. Her konfigürasyondan bir sonrakine N makinesinin geçiş fonksiyonu aracılığıyla ulaşılmaktadır yani konfigürasyonlar arasındaki geçişlerde N makinesinin kurallarına uyulmak zorundadır. 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 simüle 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
x_i,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.

1. 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\leq i,\ j\leq n^{k}}\left[\left(\bigvee _{s\in C}x_{i,j,s}\right)\scriptstyle \land \left(\bigwedge _{s,t\in C \atop s\neq 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\leq i,j\leq 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\leq 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 n^k ×n^k olup n^2k 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(n^2k) 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.