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.
Make this part of your paper trail
Save this paper to a shelf, write a review, and keep your own notes.