Probabilistically checkable proof (complexity)

From Wikipedia, the free encyclopedia

In computational complexity theory, a probabilistically checkable proof (in short PCP) is a type of proof that can be checked by a randomized verification algorithm with bounded query complexity.

The complexity class PCP is the class of decision problems that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(logn) and query complexity O(1).

The PCP theorem states that PCP = NP.

[edit] Definition

A probabilistically checkable proof system with completeness c(n) and soundness s(n) over alphabet Σ for a decision problem L, where 0 ≤ s(n) ≤ c(n) ≤ 1, is a randomized oracle Turing Machine V (the verifier) that, on input x and oracle access to a string π ∈ Σ^* (the proof), satisfies the following properties:

• Completeness: If x ∈ L then for some π, V^π(x) accepts with probability at least c(n),
• Soundness: If x ∉ L then for every π, V^π(x) accepts with probability at most s(n).

The randomness complexity r(n) of the verifier is the maximum number of random bits that V uses over all x of length n.

The query complexity q(n) of the verifier is the maximum number of queries that V makes to π over all x of length n.

The verifier is said to be non-adaptive if it makes all its queries before it receives any of the answers to previous queries.

The complexity class PCP_{c(n), s(n)}[r(n), q(n)] is the class of all decision problems having probabilistically checkable proof systems over binary alphabet of completeness c(n) and soundness s(n), where the verifier is nonadaptive, and it has randomness complexity r(n) and query complexity q(n).

The shorthand notation PCP[r(n), q(n)] is sometimes used for PCP_{1, ½}[r(n), q(n)]. The complexity class PCP is defined as PCP_{1, ½}[O(logn), O(1)].

[edit] History and Significance

The theory of probabilistically checkable proofs studies the power of probabilistically checkable proof systems under various restrictions of the parameters (completeness, soundness, randomness complexity, query complexity, and alphabet size). It has applications to computational complexity (in particular hardness of approximation) and cryptography.

The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992, although their properties were studied earlier.

For extreme settings of the parameters, the definition of probabilistically checkable proofs is easily seen to be equivalent to standard complexity classes. For example, PCP[O(log(n)), 0] = P, PCP[poly(n), 0] = coRP and PCP[0, poly(n)] = NP. (Could anyone please add the proof of those equivalence?)

In 1990 Babai, Fortnow, and Lund proved that PCP[poly(n), poly(n)] = NEXP, providing the first nontrivial equivalence between standard proofs (NEXP) and probabilistically checkable proofs. The PCP theorem proved in 1992 gives another such equivalence.

The theory of hardness of approximation requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.

[edit] References

• Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70-122, 1998.
• Oded Goldreich. Computational Complexity: A Conceptual Perspective. Cambridge University Press (2008), ISBN 978-0-521-88473-0.
• Ryan O'Donnell and Venkatesan Guruswami. A history of the PCP theorem. Course notes, University of Washington, 2005.

[edit] External links

• Subhash Khot. PCP course notes. Georgia Institute of Technology, 2004.
• Ryan O'Donnell and Venkatesan Guruswami. PCP course notes. University of Washington, 2005.