Are there interactive protocols for co-NP languages?
From MaRDI portal
Publication:1118406
DOI10.1016/0020-0190(88)90199-8zbMath0668.68054OpenAlexW1982248598MaRDI QIDQ1118406
Michael Sipser, Lance J. Fortnow
Publication date: 1988
Published in: Information Processing Letters (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/0020-0190(88)90199-8
Analysis of algorithms and problem complexity (68Q25) Complexity of computation (including implicit computational complexity) (03D15)
Related Items
The random oracle hypothesis is false, On the power of multi-prover interactive protocols, A Hierarchy Theorem for Interactive Proofs of Proximity, Structural complexity theory: Recent surprises, A tight relationship between generic oracles and type-2 complexity theory, Unnamed Item, Strong self-reducibility precludes strong immunity, The relativized relationship between probabilistically checkable debate systems, IP and PSPACE, Interactive proof systems and alternating time-space complexity, Non-deterministic exponential time has two-prover interactive protocols, Relativized isomorphisms of NP-complete sets, The generic oracle hypothesis is false, Error-bounded probabilistic computations between MA and AM, On the power of interaction, $$P\mathop{ =}\limits^{?}NP$$, Generalized lowness and highness and probabilistic complexity classes, Interactive and probabilistic proof-checking
Cites Work
