Cook-Levin teoremi: Revizyonlar arasındaki fark
| [kontrol edilmiş revizyon] | [kontrol edilmiş revizyon] |
İçerik silindi İçerik eklendi
→İspat: png --> tex |
|||
45. satır:
[[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:
Q : N makinesinin durumları kümesi
Γ : N makinesinin alfabesi
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.
:<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 />▼
# 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.
Satır 75 ⟶ 77:
İ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 />
| |||