The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace
| dc.contributor.author | Russell, Alexander | en_US |
| dc.contributor.author | Sundaram, Ravi | en_US |
| dc.date.accessioned | 2023-03-29T14:37:15Z | |
| dc.date.available | 2023-03-29T14:37:15Z | |
| dc.date.issued | 1993-09 | |
| dc.identifier.uri | https://hdl.handle.net/1721.1/149213 | |
| dc.description.abstract | In 1990, PSPACE was shown to be identical to IP, the class of languages with interactive proofs [11, 2]. Recently, PSPACE was again recharacterized, this time in terms of (Random) Probabilistically Checkable Debate Systems [4, 5]. In particular, it was shown that SPACE = PCDS[log n, 1] = RPCDS [log n, 1]. We study the relativized behaviour of the classes defined by these debates systems in comparison with the classes IP and PSPACE. | en_US |
| dc.relation.ispartofseries | MIT-LCS-TM-492 | |
| dc.title | The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace | en_US |
