The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
From MaRDI portal
Publication:673812
DOI10.1016/0020-0190(94)00185-2zbMath0875.68417OpenAlexW2041566873WikidataQ127433722 ScholiaQ127433722MaRDI QIDQ673812
Ravi Sundaram, Alexander Russell
Publication date: 28 February 1997
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(94)00185-2
Cites Work
- Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes
- Are there interactive protocols for co-NP languages?
- The random oracle hypothesis is false
- On the random oracle hypothesis
- The Knowledge Complexity of Interactive Proof Systems
- Relative to a Random OracleA, ${\bf P}^A \ne {\bf NP}^A \ne \text{co-}{\bf NP}^A $ with Probability 1
- Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
- Algebraic methods for interactive proof systems
- IP = PSPACE
- Probabilistically checkable debate systems and approximation algorithms for PSPACE-hard functions
- On the Computational Complexity of Algorithms
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
This page was built for publication: The relativized relationship between probabilistically checkable debate systems, IP and PSPACE
