PCP theorem
E74456
The PCP theorem is a fundamental result in computational complexity theory stating that every problem in NP has probabilistically checkable proofs that can be verified by examining only a constant number of bits, with major implications for the hardness of approximation.
Observed surface forms (2)
| Surface form | Occurrences |
|---|---|
| NP in terms of probabilistically checkable proofs | 1 |
| Probabilistically Checkable Proofs theorem | 1 |
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf | theorem in computational complexity theory ⓘ |
| characterizes |
PCP theorem
self-linksurface differs
ⓘ
surface form:
NP in terms of probabilistically checkable proofs
|
| field |
computational complexity theory
ⓘ
theoretical computer science ⓘ |
| fullName |
PCP theorem
self-linksurface differs
ⓘ
surface form:
Probabilistically Checkable Proofs theorem
|
| hasConsequence |
development of modern hardness-of-approximation theory
ⓘ
gap amplification techniques in reductions ⓘ tight inapproximability results for many classical optimization problems ⓘ |
| hasParameter |
completeness
ⓘ
query complexity ⓘ randomness complexity ⓘ soundness error ⓘ |
| historicalDevelopment | evolved from work on interactive proofs and multi-prover interactive proofs ⓘ |
| implies |
many NP-optimization problems are hard to approximate within certain constant factors
ⓘ
strong inapproximability bounds for Max-3SAT ⓘ strong inapproximability bounds for Max-Clique ⓘ strong inapproximability bounds for Set Cover ⓘ strong inapproximability bounds for Vertex Cover ⓘ strong inapproximability bounds for various constraint satisfaction problems ⓘ there exist fixed constants for which approximating some NP-hard problems within those factors is NP-hard ⓘ |
| importance |
central to understanding limits of efficient approximation algorithms
ⓘ
one of the most influential results in theoretical computer science of the 1990s ⓘ |
| proofType |
adaptive probabilistically checkable proofs
ⓘ
non-adaptive probabilistically checkable proofs ⓘ |
| relatedConcept |
gap-preserving reductions
ⓘ
locally decodable codes ⓘ locally testable codes ⓘ |
| relatedTheorem |
IP equals PSPACE
ⓘ
MIP equals NEXP ⓘ |
| relatesToClass |
NP
ⓘ
PCP ⓘ |
| relatesToConcept |
NP
ⓘ
NP-completeness ⓘ approximation algorithms ⓘ error-correcting codes ⓘ gap-introducing reductions ⓘ hardness of approximation ⓘ inapproximability results ⓘ interactive proofs ⓘ probabilistically checkable proofs ⓘ |
| statesThat |
NP equals PCP(log n, 1)
ⓘ
every language in NP has a probabilistically checkable proof verifiable by reading only a constant number of bits of the proof ⓘ |
| typicalFormulation | NP equals PCP(O(log n), O(1)) ⓘ |
| usesResource |
constant query complexity
ⓘ
logarithmic randomness ⓘ randomness ⓘ |
| verificationModel | randomized polynomial-time verifier ⓘ |
| verificationProperty |
verifier reads only a constant number of bits of the proof
ⓘ
verifier uses logarithmically many random bits in the input size ⓘ |
Referenced by (4)
Full triples — surface form annotated when it differs from this entity's canonical label.
this entity surface form:
NP in terms of probabilistically checkable proofs
this entity surface form:
Probabilistically Checkable Proofs theorem