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

Related Items (17)

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

This page was built for publication: Are there interactive protocols for co-NP languages?