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 language | English (US) |
|---|---|
| Pages (from-to) | 70-122 |
| Number of pages | 53 |
| Journal | Journal of the ACM |
| Volume | 45 |
| Issue number | 1 |
| DOIs | |
| State | Published - 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