Probabilistically checkable proof

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

Contents

1 Introduction and definition 2 Example 3 Results 4 Reference

Introduction and definition

The PCP theorem, proven in the early 1990's, states that every NP problem has a very efficient probabilistically checkable proof system. This theorem has the following astonishing consequence: every proof for any mathematical statement can be formalized, so that one can check whether it is correct or not by only reading a constant number of letters from it! More precisely, one can choose which letters of the proof to look at using a certain random process, and then after reading them, one can declare the proof "correct" or "false". In this process a correct proof will always be declared as such, while any attempt to prove a wrong statement will be declared false with probability at least 1/2 (repeating this process several times can detect a false proof with arbitrarily high probability less than 1).

In complexity theory, a PCP system can be viewed as an interactive proof system in which the prover is a memoryless 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 the randomness available, the more selectivity the verifier can exercise in examining the proof. Thus, PCP is actually a meta-class of complexity classes parametrized 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's 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 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(nlog n) random bits and 3n oracle queries, placing this NP-complete problem, and so all of NP, in PCP(nlog n, n).

Results

Simple special cases (poly denotes polynomial time, log denotes logarithmic time):

• PCP (poly, 0) = Co-RP
• PCP (0, poly) = 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 (log, O(1)). This is useful for proving hardness results for approximation algorithms.

Reference

• PCP lecture notes (http://www.cs.jhu.edu/~scheideler/courses/600.471_S03/lecture_8.pdf) - by Christian Scheideler
• PCP notes and slides (http://theory.lcs.mit.edu/~madhu/pcp/course.html) - by Madhu Sudan

Important complexity classes (more)

P | NP | Co-NP | NP-C | Co-NP-C | NP-hard | UP | #P | #P-C | L | NC | P-C

PSPACE | PSPACE-C | EXPTIME | EXPSPACE | BQP | BPP | RP | ZPP | PCP | IP | PH