TQBF Problemi: Revizyonlar arasındaki fark
[kontrol edilmiş revizyon] | [kontrol edilmiş revizyon] |
İçerik silindi İçerik eklendi
Değişiklik özeti yok |
Teacher0691 (mesaj | katkılar) |
||
1. satır:
{{Öksüz|date=Şubat 2018}}
'''Boolean Formülü''' içerisinde; [[boolean]] değişkenleri, sabitler {0,1} ve işlemler {<math>\land</math>, <math> \lor</math>, <math> \lnot</math>} içeren formüllerdir. Bu formüller, <math> \forall </math>(bütün hepsi) ve <math> \exists</math> (en az bir) belirleyicilerinin eklenmesiyle daha genel bir yapıya sokulabilir. <math> \forall x Q </math> ifadesi bütün ''x'' değişkenleri için ''Q'' formülü doğrudur anlamı taşımaktadır. Benzer bir şekilde; <math>\exists x Q </math> ifadesi ise bazı ''x'' değişkenleri için ''Q'' formülü doğrudur anlamı taşımaktadır.
Satır 36 ⟶ 38:
T algoritması TQBF i belirler.
Bu algoritmanın yer karmaşıklığını analiz ettiğimizde şunu gözlemleriz: Formül, içerisindeki değişken sayısı kadar çağrılır. Her seviyede
A, M [[Turing Makinesi]] tarafından <math>n^k</math> polinomsal yerde tanımlanan bir dil olsun. Şimdi A'dan TQBF e [[Polinomsal zaman]] indirgemeye çalışacağız. Bu indirgeme için bir 'w' kelimesi kullanılsın. Söyle ki; ''Q'' ancak, M makinası 'w' yi kabul ettiğinde doğru olsun.
|