Probabilistic checking of proofs
- 1 January 1998
- journal article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 45 (1) , 70-122
- https://doi.org/10.1145/273865.273901
Abstract
We give a new characterization of NP: the class NP contains exactly those languages L for which membership proofs (a proof that an input x is in L) can be verified probabilistically in polynomial time using logarithmic number of random bits and by reading sublogarithmic number of bits from the proof.We discuss implications of this characterization; specifically, we show that approximating Clique and Independent Set, even in a very weak sense, is NP-hard.Keywords
This publication has 14 references indexed in Scilit:
- The random oracle hypothesis is falseJournal of Computer and System Sciences, 1994
- The complexity of the max word problem and the power of one-way interactive proof systemscomputational complexity, 1993
- Efficient probabilistically checkable proofs and applications to approximationsPublished by Association for Computing Machinery (ACM) ,1993
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- Approximating maximum independent sets by excluding subgraphsBIT Numerical Mathematics, 1992
- Simple Constructions of Almost k‐wise Independent Random VariablesRandom Structures & Algorithms, 1992
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- On the power of two-point based samplingJournal of Complexity, 1989
- The Knowledge Complexity of Interactive Proof SystemsSIAM Journal on Computing, 1989
- Are there interactive protocols for co-NP languages?Information Processing Letters, 1988