| |
|
06 Nisan 2012, 10:31
| #1 | |
| Çevrimdışı  IF Ticaret Sayısı: (0) | TQBF Problemi Boolean Formülü içerisinde; boolean değişkenleri, sabitler {0,1} ve işlemler { Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. , Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. , Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. } içeren formüllerdir. Bu formüller, (bütün hepsi) ve Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. (en az bir) belirleyicilerinin eklenmesiyle daha genel bir yapıya sokulabilir. Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. ifadesi bütün x değişkenleri için Q formülü doğrudur anlamı taşımaktadır. Benzer bir şekilde; Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. 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 Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. ifadesi doğrudur. Çünkü, bütün doğal sayıların bir fazlası sayının kendisinden büyüktür. Fakat, Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. 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: Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. ifadesi bir belirleyici boolean formül dür. Burada Q ifadesi doğrudur. Fakat; Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. ile Bu forumdaki linkleri ve resimleri görebilmek için en az 25 mesajınız olması gerekir. 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. | |
| |  |
| IRCForumlari.NET Reklamlar |
   |
 |
| Etiketler |
| problemi, tqbf |
| Konuyu Toplam 1 Üye okuyor. (0 Kayıtlı üye ve 1 Misafir) | |
| |
Benzer Konular | ||||
| Konu | Konuyu Başlatan | Forum | Cevaplar | Son Mesaj |
| SAT Problemi | Liaaa | Ödev ve Tezler | 0 | 06 Nisan 2012 10:24 |
| Gaz Problemi | Liaaa | Sağlık Köşesi | 0 | 11 Şubat 2012 14:01 |
| tr.l problemi | Cihandar | IRCServices | 1 | 20 Ağustos 2009 00:03 |
Normal
