THE RELATIVIZED RELATIONSHIP BETWEEN PROBABILISTICALLY CHECKABLE DEBATE SYSTEMS, IP AND PSPACE

In 1990, PSPACE was shown to be identical to IP, the class of language s with interactive proofs [18,20]. Recently, PSPACE was again recharac terized, this time in terms of (Random) Probabilistically Checkable De bate Systems [7,8]. In particular, it was shown that PSPACE = PCDS [lo g n, 1] = RPCDS[log n, 1]. We study the relativized behaviour of the c lasses defined by these debate systems in comparison with the classes IP and PSPACE. For the relationships between (R)PCDS[r(n), a(n)] and I P and (R)PCDS[r(n),a(n)] and PSPACE we determine a natural boundary (i n terms of the parameters r(n) and a(n)) separating direct-simulabilit y and inequality (with probability I), In addition, we show that if Th ere Exists 0, EXP(0) = PCDS0 [log n, log n] then P not equal PSPACE.