Are there interactive protocols for co-NP languages?

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

zbMATH Keywords

interactive protocolco-NP languages

Mathematics Subject Classification ID

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

• Does co-NP have short interactive proofs ?
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• The knowledge complexity of interactive proof-systems