1992/01/01 by Sanjeev Arora, Muli Safra · 4 citations
Computer Science · #Cryptography and Data Security #Complexity and Algorithms in Graphs #Formal Methods in Verification
paper · doi:10.1109/sfcs.1992.267824
openalex publication_date 1992/01/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/29
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.>