Probabilistic checking of proofs a new characterization of NP.

Probabilistic checking of proofs a new characterization of NP.

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...

Disgrifiad llawn

Manylion Llyfryddiaeth
Cyhoeddwyd yn:Journal of the ACM 45, 1 (1998).
Prif Awdur: Arora, Sanjeev
Fformat: Erthygl
Iaith:English
Pynciau:
Theory of computation.
Computation by abstract devices.
Analysis of algorithms and problem complexity.
Mathematical logic and formal languages.
Algorithms.
Theory.
Verification.