IRCForumları - IRC ve mIRC Kullanıcılarının Buluşma Noktası

Boolean Formülü içerisinde; boolean değişkenleri, sabitler {0,1} ve işlemler {[Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...], [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...], [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...]} içeren formüllerdir.
Bu formüller,
(bütün hepsi) ve [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] (en az bir) belirleyicilerinin eklenmesiyle daha genel bir yapıya sokulabilir.

[Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ifadesi bütün x değişkenleri için Q formülü doğrudur anlamı taşımaktadır. Benzer bir şekilde; [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ifadesi ise bazı x değişkenleri için Q formülü doğrudur anlamı taşımaktadır.
Örnek olarak, doğal sayılar kümesinde [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ifadesi doğrudur. Çünkü, bütün doğal sayıların bir fazlası sayının kendisinden büyüktür. Fakat, [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ifadesi doğal sayılar kümesi için yanlıştır. Çünkü; hiçbir doğal sayının iki katı 3'e eşit değildir. Ancak biz örek uzay olarak doğal sayıları değil de gerçek sayılar alınsaydı bu ifade doğru olurdu.

Boolean formüllerin belirleyicilerle gösterilmesine, belirleyici boolean formülü denir. Burada kullanılan uzay {0,1} den oluşur. Örnek olarak:
[Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ifadesi bir belirleyici boolean formül dür. Burada Q ifadesi doğrudur. Fakat; [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ile [Üye Olmadan Linkleri Göremezsiniz. Üye Olmak için TIKLAYIN...] ifadeleri yer değiştirseydi Q yanlış olurdu.

Eğer bir belirleyici boolean formülde bütün değişken isimleri belirleyici listesinde yer alırsa buna tamamen belirlenmiş boolean formül denir. Tamamen Belirlenmiş Boolean Formüllere cümle denir ve formülü işleme sokarsak daima doğru ya da yanlış sonuç üretir. Yukarıdaki örnek bir tamamen belirlenmiş boolean formüldür. Çünkü, bütün değişkenler (x,y) belirleyici olarak yer alır. Eğer ifadesini çıkarsaydık, yukarıdaki örnek tamamen belirlenmiş boolean formül olmazdı.
Problem Tanımı

TQBF problemi bir tamamen belirlenmiş boolen formül ün doğru ya da yanlış olduğunu belirleyebilmektir. Bunun için şöyle bir dil tanımlanır.
TQBF={<Q> | Q bir doğru olan tamamen belirlenmiş boolen formül }
Teori

TQBF PSPACE-complete'dir.
Çözüm Önerisi

TQBF'in bir PSPACE-Complete olduğunu göstermek için, cümle içindeki değişkenlere değer atan bir formül bulup tekrarlayan bir şekilde değişken değerlerini inceleyip formülün doğru ya da yanlış olacağı bulunur.

PSPACE de tanımlı bütün A dillerinin TQBF e indirgendiğini göstermek için, polinomial yer ile sınırlı A ya ait bir Turing makinesi ile başlayacağız. Daha sonra, boolean formül ile kodlanarak ve A diline ait makina ile çalışacak bir kelime ile polynomial zamana indirgemeye çalışacağız. Şöyle ki, formül ancak ve ancak makina gönderilen kelimeyi kabul ederse doğru olacak.

Burada formülü oluştutmak için Savitch Teoremi kullanacağız. Yaratılacak yeni formül, ana formülü parçalara bölecek ve her bir belirleyiciyi formülde yerine koyarak daha küçük formüller yaratacak.
Çözüm

TQBF i belirleyen bir polinomsal yer algoritması oluşturacağız.
T= <Q> verisini kullanan bir tamamen belirlenmiş boolean formül.