TQBF Problemi: Revizyonlar arasındaki fark

'''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) belirleyicileri ekleyerek daha genel bir yapıya sokabiliriz. <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.

 

T= <Q> verisini kullanan bir ''tamamen belirlenmiş boolean formül''.

 

 

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 sadace bir değişken değerini tutarız. Bu yüzden toplam kullanılacak yer <math>O(m)</math>, m = toplam değişken sayısı, dır. Buradan ''T'' nin [[Lineer zaman]]da bittiğini gözlemleriz.

 

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.

 

''Q'' yu nasıl oluşturacağımızı göstermek için daha genel bir problemi çözülür. c₁ ve c₂ iki tane değişken listesi olsun. ve t>0 olan bir sayı. Öncelikle Q_c₁,c₂,t formülü kurarız. Eğer c₁ ve c₂ yi doğru bir şekilde kurarsak; formül, M makinası c₁ den c₂ ye en fazla t stepte giderse doğru olur. Bu durumda, Q_{c_start,c_accept,h}, <math>h=2^df(n)</math> alırız. Böylece ''M'' ''n'' verisi üzerinde en fazla <math>2^df(n)</math> değişik konfigürasyona sahip olur. Burada <math>f(n)=n^k</math> ve ''t'' 2 nin katı olacak şekilde alalım.

 

Eğer t=1 ise, Q_c₁,c₂,t kolayca oluşturulabilir. Böyle bir durumda, ya c₁ c₂ ye eşittir yada c₁ den c₂ ye M makinasında bir step vardır.

 

Eğer t>1 ise, Q_c₁,c₂,t formülü tekrarlarla kurulur. Şöyleki:

 

Q_c₁,c₂,t = <math>\exists</math>m₁[

 

Yeni değikenlerin eklenmesi, iki tekrarlayan formülü teke indirdi. <math>\forall</math> (c₃,c₄) <math>\in</math> {(c₁,m₁),(m₁,c₂)} ifadesiyle, c₃ ve c₄ değişkenleri sırasıyla c₁,m₁ veya m₁,c₂ değerleri alabilir. Ve Q_{c₃,c₄,t/2}] her iki durumda da doğrudur.

 

Q_{c_start,c_accept,h}, <math>h=2^df(n)</math> nin uzunluğunu hesaplarken şunu söyleyebiliriz: tekrarlayan her step genel formüle bir eleman ekler bu yüzden formülün tamamı lineer uzunluktadır.

 

==Kaynakça==

[[Kategori:Karmaşıklık kuramı]]

[[Kategori:Matematik teoremleri]]