The Complexity Of Debate Checking

Summary:

We introduce a model of probabilistic debate checking, where a silent resource-bounded verifier reads a dialogue about the membership of a given string in the language under consideration between a prover and a refuter. Our model combines and generalizes the concepts of one-way interactive proof systems, games of incomplete information, and probabilistically checkable complete-information debate systems. We consider debates of partial- and zero-information, where the prover is prevented from seeing some or all of the messages of the refuter, as well as those of complete-information. The classes of languages with debates checkable by verifiers operating under severe bounds on the time, memory, and randomness are studied. We give full characterizations of versions of these classes corresponding to simultaneous bounds of O(1) space and O(1) random bits, and logarithmic space and O(1) random bits. We further examine the power of constant-space model by giving lower bounds for the classes of languages checkable by such verifiers for any desired error bound when we loosen the randomness bound. We also examine the power of debate checking by time-bounded verifiers and show that no amount of randomness can help a time-bounded verifier to outperform its deterministic counterpart. However, we show that randomness does seem to help when we further constrain these time-bounded verifiers to use only logarithmic space in the order of their time bound. Additionally, in case of logspace and polynomial-time verifiers, we show that logarithmic randomness is sufficient to check complete- and partial-information debates for the languages in PSPACE. Finally, we show that any language having debates checkable by logspace polynomial-time verifiers can be reduced to the quantified max word problem for matrices, which allows us to present a result on the hardness of approximating this problem.

Özet:

Bu tezde ispatçı ve çürütücü adlı iki oyuncunun girdinin dil içinde olup olmadığı üzerine oluşturduğu diyoloğun sınırlı kaynaklı olasılıksal bir hakem tarafından okunduğu yeni bir münazara modeli tanımlanmaktadır. Modelimiz tek yönlü etkileşimli ispat sistemleri, noksan bilgili oyunlar ve olasılıksal kontrollü münazara modellerini birleştirir ve genelleştirir. Tam-, kısmi- ve sıfır-bilgili münazara çeşitleri ele alınmaktadır. Kısmi- ve sıfır-bilgili münazaralarda ispatçı çürütücünün mesajlarından sırayla bazılarını ve hiçbirini göremezken, tam-bilgili münazaralarda her iki oyuncu da birbirlerinin mesajlarını tamamen görürler. Zamansal, belleksel ve olasılıksal olarak sınırlı bir hakemin bu çeşitlerde münzaraları kontrol ederek hangi dil ailelerini tanıyabileceği araştırılmaktadır. O(1) bellek ve O(1) rastgelelik kullanan hakemlerin bu üç münazara çeşidi için tanıyabildiği dil sınıflarının tam tanımı yapılmaktadır. İlaveten, sonlu bellekli hakemler tarafından herhangi bir hata payı ile kontrol edilebilen sırasıyla sıfır- ve kısmi-bilgili münazaralara sahip diller kümesi için alt limitler verilmektedir. Tam- ve kısmi-bilgili münazaraların zaman-sınırlı hakemler tarafından kontrol edildiği durumun gücü de araştırıldı ve bu hakemlerin ne kadar rastgelelik kullanırlarsa kullansınlar aynı sınırlara sahip belirlenimci hakemlere bir üstünlük kuramadıkları anlaşıldı. Fakat, rastgelelik kullanılmasının bu zaman-sınırlı hakemlerin beleklerinin zaman-sınırının logaritmasına kadar indirilebilmesine izin verdiği ortaya çıktı. Ayrıca, polinom zaman ve logaritmik bellekle sınırlı hakemlerin PSPACE'teki diller için tam- ve kısmi-bilgili münazara kontrol etmesinin logaritmik rastgelelik kullanılarak da mümkün olduğu gösterilmektedir. Son olarak, polinom zaman ve logaritmik bellek kullanıp tam-bilgili münazara kontrol eden hakemlerin yapısından faydalanıp böyle münazaralara sahip dillerin nicellendirilmiş matrisler üzerinde maksimum çarpım problemine indirgenebileceği gösterilerek bu problemin yakınsanamazlığı ile ilgili bir sonuç sunulmaktadır.