StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
text
Body
copied!<p>Targeted towards the layman computer scientist:</p> <p>The PCP theorem says that you can make proofs that are so easy to check that you only need to look at a constant number of (randomly selected) bits to (usually) tell a bad proof from a good one.</p> <p>Targeted towards the layman theorist:</p> <p>For a language to be in NP means that you can <em>prove</em> a string is in the language easily. For example, you can prove a boolean circuit is satisfiable by providing its satisfying input. (but it's hard to prove a circuit is <em>not</em> satisfiable!)</p> <p>In this context the person/program/turing machine verifying the proof has to run in polynomial time (in the size of the string supposedly in the language). It must be <em>complete</em>, meaning that it always accepts a valid proof a given string is in the language. It must be <em>sound</em>, meaning it rejects any "proof" for a string that is <em>not</em> in the language.</p> <p>For NP the verifier is deterministic. What if the verifier can use randomness? We then have to allow for some error, so we allow the verifier to not be totally <em>sound</em>-- it can improperly accept some proofs. Really, all we care about is that the verifier detects bad proofs at least, say, 1/4 of the time. If you want better accuracy you can always run it a few more times! :-)</p> <p>The PCP theorem, in its strongest form, says that any language in NP has a proof system that can be verified by only looking at a <em>constant</em> number of randomly selected bits. The constant is... <strong>3</strong>. (That's the same 3 from 3-SAT) These proofs use error correcting codes, such that any error in the proof will conflict with a large portion of the input. Using a stronger code lets you get arbitrarily close to 50% soundness with just 3 bits.</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload