PCP theorem

Last updated

In computational complexity theory, the PCP theorem (also known as the PCP characterization theorem) states that every decision problem in the NP complexity class has probabilistically checkable proofs (proofs that can be checked by a randomized algorithm) of constant query complexity and logarithmic randomness complexity (uses a logarithmic number of random bits).

Contents

The PCP theorem says that for some universal constant K, for every n, any mathematical proof for a statement 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 algorithms for various optimization problems. It has been described by Ingo Wegener as "the most important result in complexity theory since Cook's theorem" [1] and by Oded Goldreich as "a culmination of a sequence of impressive works […] rich in innovative ideas". [2]

Formal statement

The PCP theorem states that

NP = PCP [O(log n), O(1)],

where PCP[r(n), q(n)] is the class of problems for which a probabilistically checkable proof of a solution can be given, such that the proof can be checked in polynomial time using r(n) bits of randomness and by reading q(n) bits of the proof, correct proofs are always accepted, and incorrect proofs are rejected with probability at least 1/2. n is the length in bits of the description of a problem instance. Note further that the verification algorithm is non-adaptive: the choice of bits of the proof to check depend only on the random bits and the description of the problem instance, not the actual bits of the proof.

PCP and hardness of approximation

An alternative formulation of the PCP theorem states that the maximum fraction of satisfiable constraints of a constraint satisfaction problem is NP-hard to approximate within some constant factor. [3]

Formally, for some constants q and α < 1, the following promise problem (Lyes, Lno) is an NP-hard decision problem:

where Φ is a constraint satisfaction problem (CSP) over a Boolean alphabet with at most q variables per constraint.

The connection to the class PCP mentioned above can be seen by noticing that checking a constant number of bits q in a proof can be seen as evaluating a constraint in q Boolean variables on those bits of the proof. Since the verification algorithm uses O(log n) bits of randomness, it can be represented as a CSP as described above with poly(n) constraints. The other characterisation of the PCP theorem then guarantees the promise condition with α = 1/2: if the NP problem's answer is yes, then every constraint (which corresponds to a particular value for the random bits) has a satisfying assignment (an acceptable proof); otherwise, any proof should be rejected with probability at least 1/2, which means any assignment must satisfy fewer than 1/2 of the constraints (which means it will be accepted with probability lower than 1/2). Therefore, an algorithm for the promise problem would be able to solve the underlying NP problem, and hence the promise problem must be NP hard.

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. This can be done by reducing the problem of approximating a solution to such problems to a promise problem of the above form. These results are sometimes also called PCP theorems because they can be viewed as probabilistically checkable proofs for NP with some additional structure.

Proof

A proof of a weaker result, NP ⊆ PCP[n3, 1] is given in one of the lectures of Dexter Kozen. [4]

History

The PCP theorem is the culmination of a long line of work on interactive proofs 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 Babai, Fortnow & Lund (1990).

Origin of the initials

The notation PCPc(n), s(n)[r(n), q(n)] is explained at probabilistically checkable proof. The notation is that of a function that returns a certain complexity class. See the explanation mentioned above.

The name of this theorem (the "PCP theorem") probably comes either from "PCP" meaning "probabilistically checkable proof", or from the notation mentioned above (or both).

First theorem [in 1990]

Subsequently, the methods used in this work were extended by Babai, Lance Fortnow, Levin, and Szegedy in 1991 ( Babai et al. 1991 ), Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 ( Arora & Safra 1992 ) to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1998 ( Arora et al. 1998 ).

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 significantly simpler proof of the PCP theorem, using expander graphs. [5] She received the 2019 Gödel Prize for this. [6]

Quantum analog

In 2012, Thomas Vidick and Tsuyoshi Ito published a result [7] that showed a "strong limitation on the ability of entangled provers to collude in a multiplayer game". This could be a step toward proving the quantum analogue of the PCP theorem, since when the result [7] was reported in the media, [8] [9] professor Dorit Aharonov called it "the quantum analogue of an earlier paper on multiprover interactive proofs" that "basically led to the PCP theorem". [9]

In 2018, Thomas Vidick and Anand Natarajan proved [10] a games variant of quantum PCP theorem under randomized reduction. It states that QMA ⊆ MIP*[log(n), 1, 1/2], where MIP*[f(n), c, s] is a complexity class of multi-prover quantum interactive proofs systems with f(n)-bit classical communications, and the completeness is c and the soundness is s. They also showed that the Hamiltonian version of a quantum PCP conjecture, namely a local Hamiltonian problem with constant promise gap c − s is QMA-hard, implies the games quantum PCP theorem.

NLTS conjecture was a fundamental unresolved obstacle and precursor to a quantum analog of PCP. [11] The NLTS conjecture was proven in 2022 by Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe. [12]

Notes

  1. ↑ Ingo Wegener (2005). Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer. p. 161. ISBN   978-3-540-21045-0.
  2. ↑ Oded Goldreich (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. p. 405. ISBN   978-0-521-88473-0.
  3. ↑ Arora, Sanjeev; Barak, Boaz (2009). Computational Complexity: a Modern Approach (PDF) (Draft). Cambridge University Press.
  4. ↑ Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. London: Springer-Verlag. pp. 119–127. ISBN   9781846282973.
  5. ↑ See the 2005 preprint, ECCC   TR05-046. The authoritative version of the paper is Dinur (2007).
  6. ↑ EATSC 2019 Gödel Prize, retrieved 2019-09-11.
  7. 1 2 Ito, Tsuyoshi; Vidick, Thomas (2012). "A multi-prover interactive proof for NEXP sound against entangled provers". 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20–23, 2012. IEEE Computer Society. pp. 243–252. arXiv: 1207.0550 . doi:10.1109/FOCS.2012.11.
  8. ↑ Hardesty, Larry (2012-07-30). "MIT News Release: 10-year-old problem in theoretical computer science falls". MIT News Office. Archived from the original on 2014-02-02. Retrieved 2012-08-10. Interactive proofs are the basis of cryptographic systems now in wide use, but for computer scientists, they're just as important for the insight they provide into the complexity of computational problems.
  9. 1 2 Hardesty, Larry (2012-07-31). "10-year-old problem in theoretical computer science falls". MIT News Office. Archived from the original on 2012-08-01. Retrieved 2012-08-10. Dorit Aharonov, a professor of computer science and engineering at Hebrew University in Jerusalem, says that Vidick and Ito's paper is the quantum analogue of an earlier paper on multiprover interactive proofs that "basically led to the PCP theorem, and the PCP theorem is no doubt the most important result of complexity in the past 20 years." Similarly, she says, the new paper "could be an important step toward proving the quantum analogue of the PCP theorem, which is a major open question in quantum complexity theory."
  10. ↑ Natarajan, A.; Vidick, T. (October 2018). "Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA". 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS). pp. 731–742. arXiv: 1801.03821 . Bibcode:2018arXiv180103821N. doi:10.1109/FOCS.2018.00075. ISBN   978-1-5386-4230-6. S2CID   53062680.
  11. ↑ "On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-08.
  12. ↑ Anshu, Anurag; Breuckmann, Nikolas P.; Nirkhe, Chinmay (2023). "NLTS Hamiltonians from Good Quantum Codes". Proceedings of the 55th Annual ACM Symposium on Theory of Computing. pp. 1090–1096. arXiv: 2206.13228 . doi:10.1145/3564246.3585114. ISBN   9781450399135. S2CID   250072529.

Related Research Articles

In computational complexity theory, a branch of computer science, bounded-error probabilistic polynomial time (BPP) is the class of decision problems solvable by a probabilistic Turing machine in polynomial time with an error probability bounded by 1/3 for all instances. BPP is one of the largest practical classes of problems, meaning most problems of interest in BPP have efficient probabilistic algorithms that can be run quickly on real modern machines. BPP also contains P, the class of problems solvable in polynomial time with a deterministic machine, since a deterministic machine is a special case of a probabilistic machine.

In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved by a computer. A computation problem is solvable by mechanical application of mathematical steps, such as an algorithm.

<span class="mw-page-title-main">NP (complexity)</span> Complexity class used to classify decision problems

In computational complexity theory, NP is a complexity class used to classify decision problems. NP is the set of decision problems for which the problem instances, where the answer is "yes", have proofs verifiable in polynomial time by a deterministic Turing machine, or alternatively the set of problems that can be solved in polynomial time by a nondeterministic Turing machine.

In computational complexity theory, the complexity class #P (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the counting problems associated with the decision problems in the set NP. More formally, #P is the class of function problems of the form "compute f(x)", where f is the number of accepting paths of a nondeterministic Turing machine running in polynomial time. Unlike most well-known complexity classes, it is not a class of decision problems but a class of function problems. The most difficult, representative problems of this class are #P-complete.

<span class="mw-page-title-main">Interactive proof system</span>

In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties: a prover and a verifier. The parties interact by exchanging messages in order to ascertain whether a given string belongs to a language or not. The prover possesses unlimited computational resources but cannot be trusted, while the verifier has bounded computation power but is assumed to be always honest. Messages are sent between the verifier and prover until the verifier has an answer to the problem and has "convinced" itself that it is correct.

<span class="mw-page-title-main">Clique problem</span> Task of computing complete subgraphs

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

<span class="mw-page-title-main">Complexity class</span> Set of problems in computational complexity theory

In computational complexity theory, a complexity class is a set of computational problems "of related resource-based complexity". The two most commonly analyzed resources are time and memory.

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, 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.

In computer science and operations research, approximation algorithms are efficient algorithms that find approximate solutions to optimization problems with provable guarantees on the distance of the returned solution to the optimal one. Approximation algorithms naturally arise in the field of theoretical computer science as a consequence of the widely believed P ≠ NP conjecture. Under this conjecture, a wide class of optimization problems cannot be solved exactly in polynomial time. The field of approximation algorithms, therefore, tries to understand how closely it is possible to approximate optimal solutions to such problems in polynomial time. In an overwhelming majority of the cases, the guarantee of such algorithms is a multiplicative one expressed as an approximation ratio or approximation factor i.e., the optimal solution is always guaranteed to be within a (predetermined) multiplicative factor of the returned solution. However, there are also many approximation algorithms that provide an additive guarantee on the quality of the returned solution. A notable example of an approximation algorithm that provides both is the classic approximation algorithm of Lenstra, Shmoys and Tardos for scheduling on unrelated parallel machines.

The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Interest Group on Algorithms and Computational Theory. The award is named in honor of Kurt Gödel. Gödel's connection to theoretical computer science is that he was the first to mention the "P versus NP" question, in a 1956 letter to John von Neumann in which Gödel asked whether a certain NP-complete problem could be solved in quadratic or linear time.

In computational complexity theory, an Arthur–Merlin protocol, introduced by Babai (1985), is an interactive proof system in which the verifier's coin tosses are constrained to be public. Goldwasser & Sipser (1986) proved that all (formal) languages with interactive proofs of arbitrary length with private coins also have interactive proofs with public coins.

In computational complexity theory, the complexity class NEXPTIME is the set of decision problems that can be solved by a non-deterministic Turing machine using time .

In computational complexity theory, the unique games conjecture is a conjecture made by Subhash Khot in 2002. The conjecture postulates that the problem of determining the approximate value of a certain type of game, known as a unique game, has NP-hard computational complexity. It has broad applications in the theory of hardness of approximation. If the unique games conjecture is true and P ≠ NP, then for many important problems it is not only impossible to get an exact solution in polynomial time, but also impossible to get a good polynomial-time approximation. The problems for which such an inapproximability result would hold include constraint satisfaction problems, which crop up in a wide variety of disciplines.

MAX-3SAT is a problem in the computational complexity subfield of computer science. It generalises the Boolean satisfiability problem (SAT) which is a decision problem considered in complexity theory. It is defined as:

<span class="mw-page-title-main">Mario Szegedy</span>

Mario Szegedy is a Hungarian-American computer scientist, professor of computer science at Rutgers University. He received his Ph.D. in computer science in 1989 from the University of Chicago after completing his dissertation titled Algebraic Methods in Lower Bounds for Computational Models. He held a Lady Davis Postdoctoral Fellowship at the Hebrew University of Jerusalem (1989–90), a postdoc at the University of Chicago, 1991–92, and a postdoc at Bell Laboratories (1992).

Shmuel (Muli) Safra is an Israeli computer scientist. He is a Professor of Computer Science at Tel Aviv University, Israel. He was born in Jerusalem.

Carsten Lund is a Danish-born theoretical computer scientist, currently working at AT&T Labs in Bedminster, New Jersey, United States.

Lance Jeremy Fortnow is a computer scientist known for major results in computational complexity and interactive proof systems. He is the Dean of the College of Computing at the Illinois Institute of Technology.

Verifiable computing enables a computer to offload the computation of some function, to other perhaps untrusted clients, while maintaining verifiable results. The other clients evaluate the function and return the result with a proof that the computation of the function was carried out correctly. The introduction of this notion came as a result of the increasingly common phenomenon of "outsourcing" computation to untrusted users in projects such as SETI@home and also to the growing desire to enable computationally-weak devices to outsource computational tasks to a more powerful computation service, as in cloud computing. The concept dates back to work by Babai et al., and has been studied under various terms, including "checking computations", "delegating computations", "certified computation", and verifiable computing. The term verifiable computing itself was formalized by Rosario Gennaro, Craig Gentry, and Bryan Parno, and echoes Micali's "certified computation".

In quantum information theory, the no low-energy trivial state (NLTS) conjecture is a precursor to a quantum PCP theorem (qPCP) and posits the existence of families of Hamiltonians with all low-energy states of non-trivial complexity. It was formulated by Michael Freedman and Matthew Hastings in 2013. An NLTS proof would be a consequence of one aspect of qPCP problems – the inability to certify an approximation of local Hamiltonians via NP completeness. In other words, an NLTS proof would be one consequence of the QMA complexity of qPCP problems. On a high level, if proved, NLTS would be one property of the non-Newtonian complexity of quantum computation. NLTS and qPCP conjectures posit the near-infinite complexity involved in predicting the outcome of quantum systems with many interacting states. These calculations of complexity would have implications for quantum computing such as the stability of entangled states at higher temperatures, and the occurrence of entanglement in natural systems. There is currently a proof of NLTS conjecture published in preprint.

References

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.