Probabilistic checking of proofs: A new characterization of NP

Sanjeev Arora, Shmuel Safra

Research output: Contribution to journalArticle

631 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)70-122
Number of pages53
JournalJournal of the ACM
Volume45
Issue number1
DOIs
StatePublished - Jan 1998

All Science Journal Classification (ASJC) codes

  • Software
  • Control and Systems Engineering
  • Information Systems
  • Hardware and Architecture
  • Artificial Intelligence

Keywords

  • F.1.2 [Computation by Abstract Devices]: Modes of Computation
  • F.1.3 [Computation by Abstract Devices]: Complexity Classes
  • F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems

Fingerprint Dive into the research topics of 'Probabilistic checking of proofs: A new characterization of NP'. Together they form a unique fingerprint.

  • Cite this