@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",

year = "1992",

month = jan,

day = "1",

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",

note = "33rd Annual Symposium on Foundations of Computer Science, FOCS 1992 ; Conference date: 24-10-1992 Through 27-10-1992",

}