PCP (complexity)
Encyclopedia
In computational complexity theory
, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm
using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate
), as used in the verifier
-based definition of the complexity class
NP
, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.
Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP[r(n),q(n)] refers to the set of decision problem
s that have probabilistically checkable proofs that can be verified in polynomial time using at most r(n) random bits and by reading at most q(n) bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem
, a major result in computational complexity theory, states that PCP[O(log n),O(1)] = NP.
The complexity class
PCP is the class of decision problems
that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(log n) and query complexity O(1).
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:
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 PCPc(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 PCP1, ½[r(n), q(n)]. The complexity class PCP is defined as PCP1, ½[O(logn), O(1)].
(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. 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 states that PCP[O(log n),O(1)] = NP.
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.
The PCP theorem and MIP = NEXP can be characterized as follows:
It is also known that PCP[r(n), q(n)] ⊆ NTIME
(2O(r(n))q(n)+poly(n)), if the verifier is constrained to be non-adaptive. For adaptive verifiers, PCP[r(n), q(n)] ⊆ NTIME
(2O(r(n)+q(n))+poly(n)). On the other hand, if NP ⊆ PCP[o(log n),o(log n)] then P = NP.
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
, a probabilistically checkable proof (PCP) is a type of proof that can be checked by a randomized algorithm
Randomized algorithm
A randomized algorithm is an algorithm which employs a degree of randomness as part of its logic. The algorithm typically uses uniformly random bits as an auxiliary input to guide its behavior, in the hope of achieving good performance in the "average case" over all possible choices of random bits...
using a bounded amount of randomness and reading a bounded number of bits of the proof. The algorithm is then required to accept correct proofs and reject incorrect proofs with very high probability. A standard proof (or certificate
Certificate (complexity)
In computational complexity theory, a certificate is a string that certifies the answer to a computation, or certifies the membership of some string in a language...
), as used in the verifier
Formal verification
In the context of hardware and software systems, formal verification is the act of proving or disproving the correctness of intended algorithms underlying a system with respect to a certain formal specification or property, using formal methods of mathematics .- Usage :Formal verification can be...
-based definition of the complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
, also satisfies these requirements, since the checking procedure deterministically reads the whole proof, always accepts correct proofs and rejects incorrect proofs. However, what makes them interesting is the existence of probabilistically checkable proofs that can be checked by reading only a few bits of the proof using randomness in an essential way.
Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The class PCP[r(n),q(n)] refers to the set of decision problem
Decision problem
In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters. For example, the problem "given two numbers x and y, does x evenly divide y?" is a decision problem...
s that have probabilistically checkable proofs that can be verified in polynomial time using at most r(n) random bits and by reading at most q(n) bits of the proof. Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. The PCP theorem
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
, a major result in computational complexity theory, states that PCP[O(log n),O(1)] = NP.
The complexity class
Complexity class
In computational complexity theory, a complexity class is a set of problems of related resource-based complexity. A typical complexity class has a definition of the form:...
PCP is the class of decision problems
Computational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
that have probabilistically checkable proofs with completeness 1, soundness α < 1, randomness complexity O(log n) and query complexity O(1).
Definition
A probabilistically checkable proof system with completeness c(n) and soundness s(n) over alphabet Σ for a decision problemComputational problem
In theoretical computer science, a computational problem is a mathematical object representing a collection of questions that computers might want to solve. For example, the problem of factoring...
L, where 0 ≤ s(n) ≤ c(n) ≤ 1, is a randomized oracle Turing Machine
Oracle machine
In complexity theory and computability theory, an oracle machine is an abstract machine used to study decision problems. It can be visualized as a Turing machine with a black box, called an oracle, which is able to decide certain decision problems in a single operation. The problem can be of any...
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 PCPc(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 PCP1, ½[r(n), q(n)]. The complexity class PCP is defined as PCP1, ½[O(logn), O(1)].
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 complexityComputational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
(in particular hardness of approximation
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
) and cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
.
The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992, although their properties were studied earlier. 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
PCP theorem
In computational complexity theory, the PCP theorem states that every decision problem in the NP complexity class has probabilistically checkable proofs of constant query complexity and logarithmic randomness complexity .The PCP theorem says that for some universal constant K, for every...
proved in 1992 states that PCP[O(log n),O(1)] = NP.
The theory of hardness of approximation
Hardness of approximation
In computer science, hardness of approximation is a field that studies the algorithmic complexity of finding near-optimal solutions to optimization problems. It complements the study of approximation algorithms by proving, for certain problems, a limit on the factors with which their solution can...
requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.
Properties
For extreme settings of the parameters, the definition of probabilistically checkable proofs is easily seen to be equivalent to standard complexity classes. For example, we have the following:- PCP[0, 0] = PP (complexity)In computational complexity theory, P, also known as PTIME or DTIME, is one of the most fundamental complexity classes. It contains all decision problems which can be solved by a deterministic Turing machine using a polynomial amount of computation time, or polynomial time.Cobham's thesis holds...
(P is defined to have no randomness and no access to a proof.) - PCP[O(log(n)), 0] = P (A logarithmic number of random bits doesn't help a polynomial time Turing machine, since it could try all possibly random strings of logarithmic length in polynomial time.)
- PCP[0,O(log(n))] = P (Without randomness, the proof can be thought of as a fixed logarithmic sized string. A polynomial time machine could try all possible logarithmic sized proofs in polynomial time.)
- PCP[poly(n), 0] = coRPRP (complexity)In complexity theory, RP is the complexity class of problems for which a probabilistic Turing machine exists with these properties:* It always runs in polynomial time in the input size...
(By definition of coRP.) - PCP[0, poly(n)] = NPNP (complexity)In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
(By the verifier-based definition of NP.)
The PCP theorem and MIP = NEXP can be characterized as follows:
- PCP[O(log n),O(1)] = NP (the PCP theorem)
- PCP[poly(n),O(1)]] = PCP[poly(n),poly(n)] = NEXP (MIP = NEXP).
It is also known that PCP[r(n), q(n)] ⊆ NTIME
NTIME
In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space....
(2O(r(n))q(n)+poly(n)), if the verifier is constrained to be non-adaptive. For adaptive verifiers, PCP[r(n), q(n)] ⊆ NTIME
NTIME
In computational complexity theory, the complexity class NTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time O, and unlimited space....
(2O(r(n)+q(n))+poly(n)). On the other hand, if NP ⊆ PCP[o(log n),o(log n)] then P = NP.
External links
- Subhash KhotSubhash KhotSubhash Khot is an Associate Professor at New York University. He is best known for his Unique games conjecture.Khot obtained his bachelor’s degree in Computer Science from the Indian Institute of Technology Bombay in 1999. He received his doctorate degree in computer science from Princeton...
. PCP course notes. New York University, 2008. - Ryan O'Donnell and Venkatesan Guruswami. PCP course notes. University of Washington, 2005.