| Revision as of 23:08, 26 December 2005 editHmonroe (talk | contribs)233 editsm it's =>it is← Previous edit | Revision as of 10:48, 16 February 2006 edit undoPierremenard (talk | contribs)1,093 edits link description a bit too gushyNext edit → | ||
| Line 39: | Line 39: | ||
| * - by Subhash Khot | * - by Subhash Khot | ||
| * - by Trevisan | * - by Trevisan | ||
| * - by Irit Dinur | * - by Irit Dinur | ||
| {{ComplexityClasses}} | {{ComplexityClasses}} | ||
Revision as of 10:48, 16 February 2006
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 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 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 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 a polynomial quantity, log denotes a logarithmic quantity):
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.
External links
- PCP lecture notes - by Christian Scheideler
- PCP notes and slides - by Madhu Sudan
- PCP course notes - by Subhash Khot
- Survey, a good starter - by Trevisan
- A simplified proof of PCP - by Irit Dinur
| Complexity classes | |
|---|---|
| Considered feasible | |
| Suspected infeasible | |
| Considered infeasible | |
| Class hierarchies | |
| Families of classes | |
| List of complexity classes | |