The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace
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...
| Main Authors: | , |
|---|---|
| Published: |
2023
|
| Online Access: | https://hdl.handle.net/1721.1/149213 |
| Summary: | 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. |
|---|