probabilistically checkable proof

Definition from Wiktionary, the free dictionary
Jump to: navigation, search

English[edit]

Noun[edit]

probabilistically checkable proof ‎(plural probabilistically checkable proofs) (abbreviated PCP)

  1. (mathematics) A reasonable proof of a computational theorem or conjecture obtained via a randomized algorithm.

See also[edit]