Name
Abstract | ||
|---|---|---|
We study 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. 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. This model combines and generalizes the concepts of one-way interactive proof systems, games of possibly incomplete information, and probabilistically checkable debate systems. We give full characterizations of the classes of languages with debates checkable by verifiers operating under simultaneous bounds of O(1) space and O(1) random bits. It turns out such verifiers are strictly more powerful than their deterministic counterparts, and allowing a logarithmic space bound does not add to this power. PSPACE and EXPTIME have zero- and partial-information debates, respectively, checkable by constant-space verifiers for any desired error bound when we omit the randomness bound. No amount of randomness can give a verifier under only a fixed time bound a significant performance advantage over its deterministic counterpart. However, randomness does seem to help verifiers with simultaneous bounds on space and time. In the case of logspace and polynomial-time verifiers, we show that logarithmic randomness is sufficient to check complete- and partial-information debates for all languages in PSPACE. Any such language can be reduced to the quantified max word problem for matrices, which allows us to present a nonapproximability result for the optimization version of this problem. |
Year | DOI | Venue |
|---|---|---|
2014 | 10.1007/s00224-014-9547-7 | Theory of Computing Systems \/ Mathematical Systems Theory |
Keywords | Field | DocType |
Incomplete information debates,Private alternation,Games,Probabilistic computation | Discrete mathematics,Combinatorics,EXPTIME,Computer science,Word problem (mathematics education),Theoretical computer science,PSPACE,Probabilistic logic,Logarithm,Gas meter prover,Complete information,Randomness | Journal |
Volume | Issue | ISSN |
57 | 1 | 1432-4350 |
Citations | PageRank | References |
1 | 0.37 | 26 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| H. Gökalp Demirci | 1 | 8 | 3.31 |
| A. C. Cem Say | 2 | 193 | 26.13 |
| Abuzer Yakaryilmaz | 3 | 168 | 25.31 |