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...
| প্রকাশিত: | Journal of the ACM 45, 1 (1998). |
|---|---|
| প্রধান লেখক: | |
| বিন্যাস: | প্রবন্ধ |
| ভাষা: | English |
| বিষয়গুলি: |