Basit öğe kaydını göster

dc.contributor Graduate Program in Computer Engineering.
dc.contributor.advisor Say, Ahmet Celal Cem.
dc.contributor.author Demirci, Hüseyin Gökalp.
dc.date.accessioned 2023-03-16T10:01:42Z
dc.date.available 2023-03-16T10:01:42Z
dc.date.issued 2013.
dc.identifier.other CMPE 2013 D46
dc.identifier.uri http://digitalarchive.boun.edu.tr/handle/123456789/12258
dc.description.abstract We introduce a model of probabilistic debate checking, where a silent resourcebounded veri er 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 veri ers 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 veri ers for any desired error bound when we loosen the randomness bound. We also examine the power of debate checking by time-bounded veri ers and show that no amount of randomness can help a timebounded veri er to outperform its deterministic counterpart. However, we show that randomness does seem to help when we further constrain these time-bounded veri ers to use only logarithmic space in the order of their time bound. Additionally, in case of logspace and polynomial-time veri ers, we show that logarithmic randomness is su - cient to check complete- and partial-information debates for the languages in PSPACE. Finally, we show that any language having debates checkable by logspace polynomialtime veri ers can be reduced to the quanti ed max word problem for matrices, which allows us to present a result on the hardness of approximating this problem.
dc.format.extent 30 cm.
dc.publisher Thesis (M.S.) - Bogazici University. Institute for Graduate Studies in Science and Engineering, 2013.
dc.subject.lcsh Fuzzy logic.
dc.subject.lcsh Probabilities.
dc.title The complexity of debate checking
dc.format.pages viii, 65 leaves ;


Bu öğenin dosyaları

Bu öğe aşağıdaki koleksiyon(lar)da görünmektedir.

Basit öğe kaydını göster

Dijital Arşivde Ara


Göz at

Hesabım