Probabilistically Checkable Proofs theorem
GPTKB entity
Statements (23)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
gptkb:mathematical_concept
|
| gptkbp:alsoKnownAs |
gptkb:PCP_theorem
|
| gptkbp:concerns |
gptkb:probabilistically_checkable_proofs
|
| gptkbp:enables |
proof verification with few random bits and queries
|
| gptkbp:field |
theoretical computer science
|
| https://www.w3.org/2000/01/rdf-schema#label |
Probabilistically Checkable Proofs theorem
|
| gptkbp:implies |
hardness of approximation results
|
| gptkbp:influencedBy |
theory of hardness of approximation
|
| gptkbp:isMilestoneIn |
gptkb:complexity_theory
|
| gptkbp:provenBy |
gptkb:Rajeev_Motwani
gptkb:Madhu_Sudan gptkb:Sanjeev_Arora gptkb:Shmuel_Safra gptkb:Carsten_Lund Mario Szegedy |
| gptkbp:publishedIn |
gptkb:Journal_of_the_ACM
|
| gptkbp:relatedTo |
gptkb:NP-completeness
approximation algorithms inapproximability |
| gptkbp:state |
NP = PCP(log n, 1)
|
| gptkbp:yearProved |
1992
|
| gptkbp:bfsParent |
gptkb:PCP_theorem
|
| gptkbp:bfsLayer |
7
|