{{Short description|Theorem in computational complexity theory}} {{distinguish | Post correspondence problem}} 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).
The PCP theorem says that for some universal constant <math>K</math>, for every <math>n</math>, any mathematical proof for a statement of length <math>n</math> can be rewritten as a different proof of length <math>\operatorname{poly}(n)</math> that is formally verifiable with 99% accuracy by a randomized algorithm that inspects only <math>K</math> 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"<ref name="Wegener2005">{{cite book|author=Ingo Wegener|title=Complexity Theory: Exploring the Limits of Efficient Algorithms|url=https://books.google.com/books?id=1fo7_KoFUPsC&pg=PA161|year=2005|publisher=Springer|isbn=978-3-540-21045-0|page=161}}</ref> and by Oded Goldreich as "a culmination of a sequence of impressive works […] rich in innovative ideas".<ref name="Goldreich2008">{{cite book|author=Oded Goldreich|title=Computational Complexity: A Conceptual Perspective|url=https://books.google.com/books?id=EuguvA-w5OEC&pg=PA405|year=2008|publisher=Cambridge University Press|isbn=978-0-521-88473-0|page=405}}</ref>
==Formal statement==
The PCP theorem states that <math display=block>\mathsf{NP}=\mathsf{PCP}[O(\log n),O(1)]</math> where <math>\mathsf{NP}</math> is the complexity class of problems solvable in nondeterministic polynomial time and where <math>\mathsf{PCP}[r(n),q(n)]</math> 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 <math>r(n)</math> bits of randomness and by reading <math>q(n)</math> bits of the proof, correct proofs are always accepted, and incorrect proofs are rejected with probability at least <math>\tfrac12</math>. The variable <math>n</math> 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 certain constraint satisfaction problem is NP-hard to approximate within some constant factor.<ref name="CompComplMA">{{cite book |last1=Arora |first1=Sanjeev |last2=Barak |first2=Boaz |date=2009 |title=Computational Complexity: a Modern Approach |url=https://theory.cs.princeton.edu/complexity/book.pdf |type=Draft |publisher=Cambridge University Press }}</ref>
Formally, for some constants <math>q</math> and <math>\alpha<1</math>, the following promise problem <math>(L_{\mathrm{yes}},L_{\mathrm{no}})</math> is an NP-hard decision problem: * <math>L_{\mathrm{yes}}=\{\Phi:</math> all constraints in <math>\Phi</math> are simultaneously satisfiable<math>\}</math> * <math>L_{\mathrm{no}}=\{\Phi:</math> every assignment satisfies fewer than an <math>\alpha</math> fraction of <math>\Phi</math>'s constraints<math>\}</math> where <math>\Phi</math> is a constraint satisfaction problem (CSP) over a Boolean alphabet with at most <math>q</math> variables per constraint.
The connection to the class <math>\mathsf{PCP}</math> mentioned above can be seen by noticing that checking a constant number of bits <math>q</math> in a proof can be seen as evaluating a constraint in <math>q</math> Boolean variables on those bits of the proof. Since the verification algorithm uses <math>O(\log n)</math> bits of randomness, it can be represented as a CSP as described above with <math>\operatorname{poly}(n)</math> constraints. The first formulation of the PCP theorem then guarantees the promise condition with <math>\alpha=\tfrac12</math>: 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 <math>\tfrac12</math>, which means any assignment must satisfy fewer than <math>\tfrac12</math> of the constraints (which means it will be accepted with probability lower than <math>\tfrac12</math>). 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,<ref>{{cite journal | last = Håstad | first = Johan | author-link = Johan Håstad | doi = 10.1145/502090.502098 | issue = 4 | journal = Journal of the ACM | mr = 2144931 | pages = 798–859 | title = Some optimal inapproximability results | volume = 48 | year = 2001}}</ref> maximum independent set in graphs,<ref>{{cite conference |first=D. |last=Zuckerman |title=Proc. 38th ACM Symp. Theory of Computing |pages=681–690 |year=2006 |doi=10.1145/1132516.1132612 |id={{ECCC|2005|05|100}}|chapter=Linear degree extractors and the inapproximability of max clique and chromatic number |isbn=1-59593-134-1|title-link=Symposium on Theory of Computing |s2cid=5713815 }}</ref> and the shortest vector problem for lattices<ref>{{cite journal | last = Bennett | first = Huck | department = Open problems column | editor-first = William | editor-last = Gasarch | editor-link = William Gasarch | doi = 10.1145/3586165.3586172 | issue = 1 | journal = SIGACT News | pages = 37–61 | title = The complexity of the shortest vector problem | url = https://www.cs.umd.edu/~gasarch/open/svp-color.pdf | volume = 54 | year = 2023}}</ref> cannot be approximated efficiently unless <math>\mathsf{P}=\mathsf{NP}</math>. 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, {{tmath|\mathsf{NP} \subseteq \mathsf{PCP}[n^3, 1]}} is given in one of the lectures of Dexter Kozen.<ref>{{Cite book|url=https://www.springer.com/gp/book/9781846282973|title=Theory of Computation|last=Kozen|first=Dexter C.|date=2006|publisher=Springer-Verlag|isbn=9781846282973|series=Texts in Computer Science|location=London|pages=119–127|language=en}}</ref>
==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 <math>\mathsf{NEXP}\subseteq\mathsf{PCP}[\operatorname{poly}(n),\operatorname{poly}(n)]</math>, proved by {{Harvtxt|Babai|Fortnow|Lund|1990}}.
=== Origin of the initials ===
The notation <math>\mathsf{PCP}_{c(n),s(n)}[r(n),q(n)]</math> 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 {{Harv|Babai|Fortnow|Levin|Szegedy|1991}}, Feige, Goldwasser, Lund, Safra, and Szegedy (1991), and Arora and Safra in 1992 {{Harv|Arora|Safra|1992}} to yield a proof of the PCP theorem by Arora, Lund, Motwani, Sudan, and Szegedy in 1998 {{Harv|Arora|Lund|Motwani|Sudan|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.<ref>See the 2005 preprint, {{ECCC|2005|05|046}}. The authoritative version of the paper is {{Harvtxt|Dinur|2007}}.</ref> She received the 2019 Gödel Prize for this. <ref>[http://eatcs.org/index.php/component/content/article/1-news/2807-2019-03-12-20-31-09 EATSC 2019 Gödel Prize], retrieved 2019-09-11.</ref>
== Quantum analogs ==
===Nonlocal games version=== A version of the PCP theorem for quantum nonlocal games would state that it is computationally hard to approximate the quantum value of a quantum nonlocal game. In 2012, Thomas Vidick and Tsuyoshi Ito published a result<ref name="LANL_Vidick_Ito"> {{cite conference | last1 = Ito | first1 = Tsuyoshi | last2 = Vidick | first2 = Thomas | arxiv = 1207.0550 | contribution = A multi-prover interactive proof for NEXP sound against entangled provers | doi = 10.1109/FOCS.2012.11 | pages = 243–252 | publisher = IEEE Computer Society | title = 53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20–23, 2012 | year = 2012| isbn = 978-0-7695-4874-6 }} </ref> 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<ref name="LANL_Vidick_Ito"/> was reported in the media,<ref name="eurekalert_2012-July_30"> {{cite web | url = http://www.eurekalert.org/pub_releases/2012-07/miot-mnr073012.php | title = MIT News Release: 10-year-old problem in theoretical computer science falls | publisher = MIT News Office | last = Hardesty | first = Larry | date = 2012-07-30 | accessdate = 2012-08-10 | archivedate = 2014-02-02 | url-status = live | archiveurl = https://web.archive.org/web/20140202165836/http://www.eurekalert.org/pub_releases/2012-07/miot-mnr073012.php | quote = 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. }} </ref><ref name="MIT_newsoffice_2012_July_31"/> professor Dorit Aharonov called it "the quantum analogue of an earlier paper on multiprover interactive proofs" that "basically led to the PCP theorem".<ref name="MIT_newsoffice_2012_July_31"> {{cite web | url = http://web.mit.edu/newsoffice/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731.html | title = 10-year-old problem in theoretical computer science falls | publisher = MIT News Office | last = Hardesty | first = Larry | date = 2012-07-31 | accessdate = 2012-08-10 | archivedate = 2012-08-01 | url-status = live | archiveurl = https://web.archive.org/web/20120801091329/http://web.mit.edu/newsoffice/2012/interactive-proofs-work-even-if-quantum-information-is-used-0731.html | quote = 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.” }} </ref>
In 2018, Thomas Vidick and Anand Natarajan proved<ref name="natarajan-vidick">{{Cite book|last1=Natarajan|first1=A.|last2=Vidick|first2=T.|title=2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS) |chapter=Low-Degree Testing for Quantum States, and a Quantum Entangled Games PCP for QMA |date=October 2018|pages=731–742|doi=10.1109/FOCS.2018.00075|arxiv=1801.03821|bibcode=2018arXiv180103821N|isbn=978-1-5386-4230-6|s2cid=53062680 }}</ref> a games variant of quantum PCP theorem under randomized reduction. It states that <math>\mathsf{QMA}\subseteq\mathsf{MIP}^*[\log n,1,\tfrac12]</math>, where <math>\mathsf{MIP}^*[f(n),c,s]</math> is a complexity class of multi-prover quantum interactive proofs systems with <math>f(n)</math>-bit classical communications, and the completeness is <math>c</math> and the soundness is <math>s</math>.
===Hamiltonian version=== A version of the PCP theorem for quantum local Hamiltonians would state that it is computationally hard to approximate the ground energy of a quantum local Hamiltonian. The work of Natarajan and Vidick<ref name="natarajan-vidick" /> also showed that a quantum Hamiltonian version of the PCP theorem, namely the existence of local Hamiltonian problem with constant promise gap <math>c-s</math> which are QMA-hard, implies a quantum nonlocal games version of the PCP theorem.
The NLTS conjecture was an unresolved obstacle and precursor to a quantum Hamiltonian analog of the PCP theorem.<ref>{{Cite web |date=2021-06-30 |title=On the NLTS Conjecture |url=https://simons.berkeley.edu/talks/nlts-conjecture |access-date=2022-08-08 |website=Simons Institute for the Theory of Computing |language=en}}</ref> The conjecture was proven in 2022 by Anurag Anshu, Nikolas Breuckmann, and Chinmay Nirkhe using a construction of a Hamiltonian based on quantum CSS codes.<ref>{{Cite book |last1=Anshu |first1=Anurag |title=Proceedings of the 55th Annual ACM Symposium on Theory of Computing |last2=Breuckmann |first2=Nikolas P. |last3=Nirkhe |first3=Chinmay |date=2023 |isbn=9781450399135 |pages=1090–1096 |chapter=NLTS Hamiltonians from Good Quantum Codes |doi=10.1145/3564246.3585114 |arxiv=2206.13228 |s2cid=250072529}}</ref> However, the ground states of such Hamiltonians are given explicitly by the code states of the corresponding CSS code, and thus are not computationally hard enough for a general proof of a quantum PCP theorem.
==Notes== {{Reflist}}
==References== *{{citation|last1=Arora|first1=Sanjeev|author1-link=Sanjeev Arora (computer scientist)|last2=Lund|first2=Carsten|author2-link=Carsten Lund|last3=Motwani|first3=Rajeev|author3-link=Rajeev Motwani|last4=Sudan|first4=Madhu|author4-link=Madhu Sudan|last5=Szegedy|first5=Mario|author5-link=Mario Szegedy|title=Proof verification and the hardness of approximation problems|journal=Journal of the ACM|volume=45|issue=3|year=1998|pages=501–555|doi=10.1145/278298.278306|s2cid=8561542 }}. *{{citation|last1=Arora|first1=Sanjeev|author1-link=Sanjeev Arora (computer scientist)|last2=Safra|first2=Shmuel|author2-link=Shmuel Safra|title=Approximating clique is NP-complete|journal=In Proceedings of the 33rd IEEE Symposium on Foundations on Computer Science|volume=41|issue=1|pages=2–13|year=1992}} *{{citation|last1=Arora|first1=Sanjeev|author1-link=Sanjeev Arora (computer scientist)|last2=Safra|first2=Shmuel|author2-link=Shmuel Safra|title=Probabilistic checking of proofs: A new characterization of NP|journal=Journal of the ACM|volume=45|issue=1|pages=70–122|year=1998|doi=10.1145/273865.273901|s2cid=751563 |doi-access=free}}. *{{Citation | last1=Babai | first1=László | author1-link=László Babai | last2=Fortnow | first2=Lance | author2-link=Lance Fortnow | last3=Levin | first3=Leonid | author3-link=Leonid Levin | last4=Szegedy | first4=Mario | author4-link=Mario Szegedy | title=STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing | publisher=ACM | isbn=978-0-89791-397-3 | year=1991 | chapter=Checking computations in polylogarithmic time | pages=21–32}}. *{{Citation | last1=Babai | first1=László | author1-link=László Babai | last2=Fortnow | first2=Lance | author2-link=Lance Fortnow | last3=Lund | first3=Carsten | title=SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science | publisher=IEEE Computer Society | isbn=978-0-8186-2082-9 | year=1990 | chapter=Nondeterministic exponential time has two-prover interactive protocols | pages=16–25}}. *{{citation|last=Dinur|first=Irit|authorlink=Irit Dinur|title=The PCP theorem by gap amplification|journal=Journal of the ACM|volume=54|issue=3|year=2007|doi=10.1145/1236457.1236459|pages=12–es|s2cid=53244523 }}. *{{Citation | last1=Feige | first1=Uriel | author1-link=Uriel Feige | last2=Goldwasser | first2=Shafi | author2-link=Shafi Goldwasser | last3=Lovász | first3=László | author3-link=László Lovász | last4=Safra | first4=Shmuel | author4-link=Shmuel Safra | last5=Szegedy | first5=Mario | author5-link=Mario Szegedy | title=Interactive proofs and the hardness of approximating cliques | url=http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf | publisher=ACM | doi=10.1145/226643.226652 | year=1996 | journal=Journal of the ACM | issn=0004-5411 | volume=43 | issue=2 | pages=268–292 | doi-access=free | access-date=2010-05-24 | archive-date=2011-06-10 | archive-url=https://web.archive.org/web/20110610152928/http://groups.csail.mit.edu/cis/pubs/shafi/1996-jacm.pdf | url-status=dead }}. {{DEFAULTSORT:Quantum PCP theorem}} Category:Randomized algorithms Category:Theorems in computational complexity theory Category:Quantum information theory