Probabilistically Checkable Debate Systems and Approximation Algorithms for PSPACE-Hard Functions

We initiate an investigation of probabilistically checkable debate systems (PCDS's), a natural generalization of the probabilistically checkable proof systems studied in [ALMSS, AS, BFLS, FGLSS]. In a PCDS for language L, there are two computationally powerful players, 1 and 0,a probabilistic polynomial-time verifier V, and an input x. Players 1 and 0 play a game in which they alternate writing out strings on a debate tape pi. Player 1's goal is to convince V that x epsilon L, and player 0's goal is to convince V that x not equal to epsilon L.