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

Whakaahuatanga katoa

Ngā taipitopito rārangi puna kōrero

I whakaputaina i:	Journal of the ACM 45, 1 (1998).
Kaituhi matua:	Arora, Sanjeev
Hōputu:	Tuhinga
Reo:	Ingarihi
Ngā marau:	Theory of computation. Computation by abstract devices. Analysis of algorithms and problem complexity. Mathematical logic and formal languages. Algorithms. Theory. Verification.