probabilistically checkable proof
Definition from Wiktionary, the free dictionary
English[edit]
Noun[edit]
probabilistically checkable proof (plural probabilistically checkable proofs) (abbreviated PCP)
- (mathematics) A reasonable proof of a computational theorem or conjecture obtained via a randomized algorithm.
See also[edit]
- PCP (complexity) on Wikipedia.Wikipedia:PCP (complexity)