PCP (complexity)

In computational complexity theory, PCP is the class of decision problems having probabilistically checkable proof systems.

Introduction and definition

In complexity theory, a PCP system can be viewed as an interactive proof system in which the prover is a memory-less oracle (essentially a string) and the verifier is a polynomial-time randomized algorithm. For an input which belongs to the language (a YES-instance), there exists an oracle (or proof) for which the verifier accepts with certainty; for NO-instances, the verifier rejects with probability at least 1/2, whatever be the oracle (compare Co-RP).

Another way of looking at PCP is as a more powerful version of NP. For languages in NP, the time spent checking the proof is at least as long as the proof itself, while this need not be the case for languages in PCP. Thus much longer proofs are possible for PCP than for NP.

Observe that in the above, we have not set a bound on the number of oracle queries the verifier can make. Another factor that affects the power of the PCP system is the number of coin tosses the verifier can make: the more randomness available, the more selectivity the verifier can exercise in examining the proof. Thus, PCP is actually a meta-class of complexity classes parameterized by two functions.

PCP("r"(·), "q"(·)) is the class of languages having probabilistically checkable proofs in which the verifier can make "r"("n") coin tosses and "q"("n") oracle queries on an input of size "n".

Example

Although it is difficult to describe most PCP algorithms explicitly, we can demonstrate the idea with a simple algorithm for 3CNFSAT, the version of the boolean satisfiability problem where the formula is in conjunctive normal form with exactly three literals in each clause.

Suppose we have a formula "F" with "m" variables and "n" clauses. We ask the prover to give a satisfying assignment for all "m" variables. However, we won't look at all "m"; instead, we'll use up O(log "n") random bits to choose a clause at random. We then look at the variables used in this clause and retrieve their values with only three oracle queries. If they satisfy the clause, then because the verifier chose the clause, it can be confident with probability 1/"n" that the assignment is satisfying. If the algorithm is repeated "n" times, we can achieve a constant error bound with only O("n"log "n") random bits and 3"n" oracle queries, placing this NP-complete problem, and so all of NP, in PCP("n"log "n", "n").

Results

Simple special cases ("poly" denotes a polynomial quantity, "log" denotes a logarithmic quantity):
* PCP "(0, 0)" =P
* PCP "(poly, 0)" = Co-RP
* PCP "(log, 0)" = NP

Notable facts:
* PCP "(poly, poly)" = NEXP
* If NP = PCP "(o(log), o(log))" then NP = P
* NP = PCP "(log, poly)"

The PCP theorem, one of the crowning jewels of complexity theory, states: NP = PCP "(O(log n), O(1))". This is useful for proving hardness results for approximation algorithms.

External links

* [http://theory.lcs.mit.edu/~madhu/pcp/course.html PCP notes and slides] - by Madhu Sudan
* [http://www.cc.gatech.edu/~khot/pcp-course.html PCP course notes] - by Subhash Khot
* [http://www.cs.berkeley.edu/~luca/pubs/inapprox.ps Survey, a good starter] - by Luca Trevisan
* [http://www.cs.huji.ac.il/~dinuri/mypapers/combpcp.pdf A simplified proof of PCP] - by Irit Dinur