A note on PCP vs. MIP

DOI10.1016/0020-0190(96)00043-9zbMath0875.68428OpenAlexW2160227905WikidataQ62398509 ScholiaQ62398509MaRDI QIDQ1350618

Amnon Ta-Shma

Publication date: 27 February 1997

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0020-0190(96)00043-9

zbMATH Keywords

AlgorithmsComplexityInteractive proof system

Mathematics Subject Classification ID

Parallel algorithms in computer science (68W10) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Related Items (1)

Hardness of approximate two-level logic minimization and PAC learning with membership queries

Cites Work

• On the power of multi-prover interactive protocols
• Efficient probabilistically checkable proofs and applications to approximations
• Unnamed Item

This page was built for publication: A note on PCP vs. MIP