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 |
| _version_ | 1826194155462721536 |
|---|---|
| author | Russell, Alexander Sundaram, Ravi |
| author_facet | Russell, Alexander Sundaram, Ravi |
| author_sort | Russell, Alexander |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T09:51:46Z |
| id | mit-1721.1/149213 |
| institution | Massachusetts Institute of Technology |
| last_indexed | 2024-09-23T09:51:46Z |
| publishDate | 2023 |
| record_format | dspace |
| spelling | mit-1721.1/1492132023-03-30T04:07:30Z The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace Russell, Alexander Sundaram, Ravi 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. 2023-03-29T14:37:15Z 2023-03-29T14:37:15Z 1993-09 https://hdl.handle.net/1721.1/149213 MIT-LCS-TM-492 application/pdf |
| spellingShingle | Russell, Alexander Sundaram, Ravi The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace |
| title | The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace |
| title_full | The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace |
| title_fullStr | The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace |
| title_full_unstemmed | The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace |
| title_short | The Revitalized Relationship Between Probabilistically Checkable Debate Systems, IP, and PSpace |
| title_sort | revitalized relationship between probabilistically checkable debate systems ip and pspace |
| url | https://hdl.handle.net/1721.1/149213 |
| work_keys_str_mv | AT russellalexander therevitalizedrelationshipbetweenprobabilisticallycheckabledebatesystemsipandpspace AT sundaramravi therevitalizedrelationshipbetweenprobabilisticallycheckabledebatesystemsipandpspace AT russellalexander revitalizedrelationshipbetweenprobabilisticallycheckabledebatesystemsipandpspace AT sundaramravi revitalizedrelationshipbetweenprobabilisticallycheckabledebatesystemsipandpspace |