Cook-Levin teoremi
İ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:
SAT problemini polinom zamanda doğrulayan bir Turing Makinesi(TM) tasarlamalıyız.
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, x1, x2, x3,...., xk’nin de bu ifadenin bir değişkeni olsun ve makine girdi olarak < ∅, x1, x2, x3,...., xk > katarını alsın.
Deterministik olmayacak şekilde boolean ifadedeki değişkenlere “doğru ve yanlış” değerlerini ata.
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 nk 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.
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
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.
Ş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.
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.