Probabilistically checkable proofs and local queries
Research context
postgraduate concept · established · As of 2026-10-10
The PCP theorem expresses NP=PCP(O(log n),O(1)): a polynomial-time verifier uses logarithmically many random bits and queries a constant number of positions in a polynomial-length proof, with completeness one and bounded soundness such as one-half.
Key knowledge
The PCP theorem expresses NP=PCP(O(log n),O(1)): a polynomial-time verifier uses logarithmically many random bits and queries a constant number of positions in a polynomial-length proof, with completeness one and bounded soundness such as one-half. Random access to the proof is part of the model. This is not a claim that an arbitrary written proof can be checked reliably by reading a few sentences without encoding it.
Conditions and scope
- Input length n, proof-oracle access, uniform verifier and completeness/soundness conventions are explicit.
- Proof length, encoding construction and hidden constants matter for practical verification.
Sources · 1
References
Sources retain their recorded scope. A source link alone does not establish verification of every statement.
Evidence and review
Author checked this English statement, displayed equation where present and stated hypotheses against these source locations: NP=PCP(O(log n),O(1)), completeness/soundness and proof-oracle model. The check is bounded to the recorded claims; no complete proof reconstruction, software proof replay or universal literature completeness is claimed.
2026-10-10 · Author source-body/statement/equation/domain check, with graph associations scoped individually. Separate independent content/source/inventory review is required before branch closure.
Entry details
Permanent link to this entry ↗- Record identity
- research-info-pcp-oracle-model
- Revision
- research.1
- Structured reference record
- Postgraduate & research reference