PCP theorem
Encyclopedia
In computational complexity
theory, the PCP theorem states that every decision problem
in the NP
complexity class
has probabilistically checkable proofs (proof
s that can be checked by a randomized algorithm
) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).
The PCP theorem says that for some universal constant K, for every n, any mathematical proof of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy by a randomized algorithm
that inspects only K letters of that proof.
The PCP theorem is the cornerstone of the theory of computational hardness of approximation
, which investigates the inherent difficulty in designing efficient approximation algorithm
s for various optimization problems.
The PCP theorem states that
is NP-hard
to approximate within some constant factor.
Formally, for some constants K and α < 1, the following promise problem (Lyes, Lno) is an NP-hard decision problem:
where Φ is a constraint satisfaction problem
over Boolean alphabet with at most K variables per constraint.
As a consequence of this theorem, it can be shown that the solutions to many natural optimization problems including maximum boolean formula satisfiability
, maximum independent set in graphs, and the shortest vector problem
for lattices cannot be approximated efficiently unless P = NP. These results are sometimes also called PCP theorems because they can be viewed as probabilistically checkable proofs for NP with some additional structure.
s and probabilistically checkable proofs. The first theorem relating standard proofs and probabilistically checkable proofs is the statement that NEXP ⊆ PCP[poly(n), poly(n)], proved by .
Subsequently, the method used in this work were extended by Babai, Fortnow, Levin, and Szegedy in 1991 ,
Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1992 .
The 2001 Gödel Prize
was awarded to Sanjeev Arora
, Uriel Feige
, Shafi Goldwasser
, Carsten Lund
, László Lovász
, Rajeev Motwani
, Shmuel Safra
, Madhu Sudan
, and Mario Szegedy
for work on the PCP theorem and its connection to hardness of approximation.
In 2005 Irit Dinur
discovered a different proof of the PCP theorem, using expander graph
s.
Computational Complexity
Computational Complexity may refer to:*Computational complexity theory*Computational Complexity...
theory, the PCP theorem states that every 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...
in the NP
NP (complexity)
In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
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:...
has probabilistically checkable proofs (proof
Mathematical proof
In mathematics, a proof is a convincing demonstration that some mathematical statement is necessarily true. Proofs are obtained from deductive reasoning, rather than from inductive or empirical arguments. That is, a proof must demonstrate that a statement is true in all cases, without a single...
s 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...
) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).
The PCP theorem says that for some universal constant K, for every n, any mathematical proof of length n can be rewritten as a different proof of length poly(n) that is formally verifiable with 99% accuracy 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...
that inspects only K letters of that proof.
The PCP theorem is the cornerstone of the theory of computational 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...
, which investigates the inherent difficulty in designing efficient approximation algorithm
Approximation algorithm
In computer science and operations research, approximation algorithms are algorithms used to find approximate solutions to optimization problems. Approximation algorithms are often associated with NP-hard problems; since it is unlikely that there can ever be efficient polynomial time exact...
s for various optimization problems.
The PCP theorem states that
- NPNP (complexity)In computational complexity theory, NP is one of the most fundamental complexity classes.The abbreviation NP refers to "nondeterministic polynomial time."...
= PCP[O(log n), O(1)].
PCP and hardness of approximation
An alternative formulation of the PCP theorem states that the maximum fraction of satisfiable constraints of a constraint satisfaction problemConstraint satisfaction problem
Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
to approximate within some constant factor.
Formally, for some constants K and α < 1, the following promise problem (Lyes, Lno) is an NP-hard decision problem:
- Lyes = {Φ: all constraints in Φ are simultaneously satisfiable}
- Lno = {Φ: every assignment satisfies fewer than an α fraction of Φ's constraints},
where Φ is a constraint satisfaction problem
Constraint satisfaction problem
Constraint satisfaction problems s are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations. CSPs represent the entities in a problem as a homogeneous collection of finite constraints over variables, which is solved by constraint...
over Boolean alphabet with at most K variables per constraint.
As a consequence of this theorem, it can be shown that the solutions to many natural optimization problems including maximum boolean formula satisfiability
Boolean satisfiability problem
In computer science, satisfiability is the problem of determining if the variables of a given Boolean formula can be assigned in such a way as to make the formula evaluate to TRUE...
, maximum independent set in graphs, and the shortest vector problem
Lattice problems
In computer science, lattice problems are a class of optimization problems on lattices. The conjectured intractability of such problems is central to construction of secure lattice-based cryptosystems...
for lattices cannot be approximated efficiently unless P = NP. These results are sometimes also called PCP theorems because they can be viewed as probabilistically checkable proofs for NP with some additional structure.
History
The PCP theorem is the culmination of a long line of work on interactive proofInteractive proof
Interactive proof can refer to:*Interactive proof system*Interactive theorem proving...
s and probabilistically checkable proofs. The first theorem relating standard proofs and probabilistically checkable proofs is the statement that NEXP ⊆ PCP[poly(n), poly(n)], proved by .
Subsequently, the method used in this work were extended by Babai, Fortnow, Levin, and Szegedy in 1991 ,
Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1992 .
The 2001 Gödel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
was awarded to Sanjeev Arora
Sanjeev Arora
Sanjeev Arora is a theoretical computer scientist who is best known for his work on probabilistically checkable proofs and, in particular, the PCP theorem. He is currently the Charles C...
, Uriel Feige
Uriel Feige
Uriel Feige is an Israeli computer scientist who was a doctoral student of Adi Shamir. He is notable for co-inventing the Feige–Fiat–Shamir identification scheme along with Amos Fiat and Adi Shamir...
, Shafi Goldwasser
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
, Carsten Lund
Carsten Lund
Carsten Lund is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Florham Park, New Jersey, United States.Lund was born in Aarhus, Denmark, and received the...
, László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
, Rajeev Motwani
Rajeev Motwani
Rajeev Motwani was a professor of Computer Science at Stanford University whose research focused on theoretical computer science. He was an early advisor and supporter of companies including Google and PayPal, and a special advisor to Sequoia Capital. He was a winner of the Gödel Prize in...
, Shmuel Safra
Shmuel Safra
Shmuel Safra is a Professor of Computer Science at Tel Aviv University, Israel. Born in Jerusalem.Safra's research areas include Complexity Theory and Automata Theory...
, Madhu Sudan
Madhu Sudan
Madhu Sudan is an Indian computer scientist, professor of computer science at the Massachusetts Institute of Technology and a member of MIT Computer Science and Artificial Intelligence Laboratory.-Career:...
, and Mario Szegedy
Mario Szegedy
Mario Szegedy is a Hungarian computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago...
for work on the PCP theorem and its connection to hardness of approximation.
In 2005 Irit Dinur
Irit Dinur
Irit Dinur is an Israeli mathematician. She is currently professor of computer science at the Weizmann Institute of Science. Her research is in foundations of computer science and in combinatorics, especially probabilistically checkable proofs, hardness of approximation. She graduated from the...
discovered a different proof of the PCP theorem, using expander graph
Expander graph
In combinatorics, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion as described below...
s.