Everything About ___
Live briefing

Everything about Probabilistically checkable proof

Proof checkable by a randomized algorithm

In computational complexity theory, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof, as used in the verifier-based definition of the complexity class NP, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way. Wikipedia →

🧭 Start here: a 6-step reading path

  1. Read the overview: Probabilistically checkable proofA 5-minute orientation
  2. Read the landmark paper: Fast approximate probabilistically checkable proofsCited 29 times
  3. Go sideways: PCP theoremA closely related topic
  4. Go sideways: MAX-3SATA closely related topic

📖 Definitions

Noun A reasonable proof of a computational theorem or conjecture obtained via a randomized algorithm.

🗂️ The subject at a glance

  1. Definition
  2. History and significance
  3. Properties
  4. Linear PCP

🏆 Landmark papers (most cited)

📚 Books worth reading

Open Library didn't respond; try again in a moment.

🔗 Related topics