flâneur

PCP theorem - Wikipedia

en.wikipedia.org · 2,485 words · saved by 1 readers

In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits). The PCP theorem says that for some universal constant K, for every n, any mathematical proof for a statement of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only K letters of that proof. The PCP theorem is the cornerstone of the theory of computational hardness of approximation, which investigates the inherent difficulty in designing efficient approximation algorithms for various optimization problems. It has been described by Ingo Wegener as "the most important result in complexity theory since Cook's theorem"[1] and by

PCP theorem - Wikipedia Jump to content From Wikipedia, the free encyclopedia Theorem in computational complexity theory Not to be confused with Post correspondence problem . In computational complexity theory , the PCP theorem (also known as the PCP characterization theorem ) states that every decision problem in the NP complexity class has probabilistically checkable proofs ( proofs that can be checked by a randomized algorithm ) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits). The PCP theorem says that for some universal constant

related reading