@inproceedings{5132927b542a454d869f086571c87268,
title = "Probabilistic checking of proofs; A new characterization of NP",
abstract = "The authors 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 sub-logarithmic number of queries to the proof. This is a non-relativizing characterization of NP. They discuss implications of this characterization; specifically, they show that approximating clique (or independent set) is NP-hard.",
author = "S. Arora and S. Safra",
note = "Publisher Copyright: {\textcopyright} 1992 IEEE.; 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 ; Conference date: 24-10-1992 Through 27-10-1992",
year = "1992",
doi = "10.1109/SFCS.1992.267824",
language = "English (US)",
series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",
publisher = "IEEE Computer Society",
pages = "2--13",
booktitle = "Proceedings - 33rd Annual Symposium on Foundations of Computer Science, FOCS 1992",
address = "United States",
}