Efficient Probabilistically Checkable Debates Andrew Drucker

摘要

Probabilistically checkable debate systems (PCDSs) are de bates between two competing provers, in which a polynomial-time ver ifier inspects a constant number of bits of the debate. It was shown by Condon, Feigenbaum, Lund, and Shor that every language in PSPACE has a PCDS in which the debate length is polynomially bounded. Using this result, they showed that the approximation versions of some natural PSPACE-complete problems are also PSPACE-complete. We give an improved construction of these debates: for any language L that has an ordinary debate system definable by uniform circuits of size s = s(n), we give a PCDS for L whose debate is of total bitlength O(s), with a verifier that uses only log_2 s+log_2(polylog(s)) bits of randomness. This yields a much tighter connection between the time complexity of natural PSPACE-complete problems and the time complexity of their approximation versions. Our key ingredient is a novel application of error-resilient commu nication protocols, as developed by Schulman; we use the more recent protocol of Braverman and Rao. We show that by requiring ordinary debates to be encoded in an error-resilient fashion, we can endow them with a useful "stability" property. Stable debates can then be trans formed into PCDSs, by applying efficient PCPPs (as given by Dinur). Our main technical challenge in building stable debates is to enforce error-resilient encoding by the debaters. To achieve this, we show that there is a constant-round debate system, with a very efficient verifier, to debate whether a communication transcript follows the Braverman-Rao protocol.