Citation
S. Arora et S. Safra, PROBABILISTIC CHECKING OF PROOFS - A NEW CHARACTERIZATION OF NP, JOURNAL OF THE ACM, 45(1), 1998, pp. 70-122
Citations number
59
Categorie Soggetti
Computer Science Hardware & Architecture","Computer Science Information Systems","Computer Science Software Graphycs Programming","Computer Science Theory & Methods","Computer Science Hardware & Architecture","Computer Science Information Systems","Computer Science Software Graphycs Programming","Computer Science Theory & Methods
Journal title
Volume
45
Issue
1
Year of publication
1998
Pages
70 - 122
Database
ISI
SICI code
Abstract
We give a new characterization of NP: the class NP contains exactly th
ose languages L for which membership proofs (a proof that an input x i
s in L) can be verified probabilistically in polynomial time using log
arithmic 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.