PCP Theorem

Question

Could somebody describe the PCP Theorem in layman's terms? [edit:Im a computer science student beginning theory.]

Answer 1

Well, Wikipedia has at least two pages on the subject:

• Probabilistically Checkable Proof (complexity)
• PCP Theorem

What level of knowledge can we assume for your layman?

Roughly speaking, I think, it says that is possible to check that a given solution to an NP complete problem is close to optimal within a (reasonable) finite time, whereas determining the optimal solution is not.

However, that assumes you know that 'NP complete' means a problem that has a 'non-deterministic polynomial complexity', and so on -- which is quite an assumption for a layman. You need to understand complexity theory and 'big-O' notation well enough to know what that means. And to understand that there is a huge division between the algorithms with (deterministic) polynomial time characteristics and those with non-deterministic polynomial time characteristics.

In this, Wikipedia will be your friend - or the algorithm books recommended by your instructor.

---

Corrected based on comments from Jörg W Mittag - thanks.

Answer 2

you might try "every problem in NP has a PCP", but "laymen" probably don't care about this topic and any explanation in depth risks boring them into a coma ;-)

Answer 3

Targeted towards the layman computer scientist:

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.

Targeted towards the layman theorist:

For a language to be in NP means that you can prove 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 not satisfiable!)

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 complete, meaning that it always accepts a valid proof a given string is in the language. It must be sound, meaning it rejects any "proof" for a string that is not in the language.

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 sound-- 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! :-)

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 constant number of randomly selected bits. The constant is... 3. (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.