Cook-Levin teoremi: Revizyonlar arasındaki fark

→‎İspat: png --> tex
k (Bot: Artık Vikiveri tarafından d:q377276 sayfası üzerinden sağlanan 15 vikilerarası bağlantı taşınıyor)
(→‎İspat: png --> tex)
 
[[Dosya:Sat tablo.png|left|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 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:<br />
 
Q : N makinesinin durumları kümesi<br />
 
Γ : N makinesinin alfabesi<br />
 
C = Q ∪ Γ ∪ {#} : Tablodaki değişkenler kümesi<br />
x<sub>i,j,s</sub> : ∅ 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.<br />
 
[[Dosya:Sat c def.png|388 × 81px]]<br />
:<math>\begin{array}{l} \bigvee_{s\in C}x_{i,j,s}=x_{i,j,s_1}\and x_{i,j,s_2}\and\ldots\and x_{i,j,s_l} \\ C=\{s_1,s_2,\ldots,s_l\} \end{array}</math>
Şimdi F ifadesinin ne gibi koşulları sağlaması gerektiğine bakalım.<br />
 
Şimdi F ifadesinin ne gibi koşulları sağlaması gerektiğine bakalım.<br />
 
# 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.
İndirgemenin karmaşıklığını göstermek için ∅ formülünün boyutu göstermek yeterli olacaktır. Tablonun boyutu n<sup>k</sup> ×n<sup>k</sup> olup n<sup>2k</sup> 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<sup>2k</sup> )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;<br />
1

düzenleme