PCP theorem

PCP theorem Not to be confused with 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 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] Contents 1 Formal statement 2 PCP and hardness of approximation 3 Proof 4 History 4.1 Origin of the initials 4.2 First theorem [in 1990] 4.3 Quantum analog 5 Notes 6 References Formal statement The PCP theorem states that NP = 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 problem 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: Lyes = {Φ: all constraints in Φ are simultaneously satisfiable} Lno = {Φ: every assignment satisfies fewer than an α fraction of Φ's constraints}, 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. Proof A proof of a weaker result, NP = PCP[n3, 1] is given in one of the lectures of Dexter Kozen.[3] 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] This article possibly contains inappropriate or misinterpreted citations that do not verify the text. Please help improve this article by checking for citation inaccuracies. (April 2016) (Learn how and when to remove this template message) 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.[4] She received the 2019 Gödel Prize for this. [5] Quantum analog In 2012, Thomas Vidick and Tsuyoshi Ito published a result[6] 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[6] was reported in the media,[7][8] professor Dorit Aharonov called it "the quantum analogue of an earlier paper on multiprover interactive proofs" that "basically led to the PCP theorem".[8] In 2018, Thomas Vidick and Anand Natarajan proved[9] 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 is a fundamental unresolved obstacle and precursor to a quantum analog of PCP.[10] Notes ^ Ingo Wegener (2005). Complexity Theory: Exploring the Limits of Efficient Algorithms. Springer. p. 161. ISBN 978-3-540-21045-0. ^ Oded Goldreich (2008). Computational Complexity: A Conceptual Perspective. Cambridge University Press. p. 405. ISBN 978-0-521-88473-0. ^ Kozen, Dexter C. (2006). Theory of Computation. Texts in Computer Science. London: Springer-Verlag. pp. 119–127. ISBN 9781846282973. ^ See the 2005 preprint, ECCC TR05-046. The authoritative version of the paper is Dinur (2007). ^ EATSC 2019 Gödel Prize, retrieved 2019-09-11. ^ Jump up to: a b Ito, Tsuyoshi; Vidick, Thomas (2012). "A multi-prover interactive proof for NEXP sound against entangled provers". arXiv:1207.0550 [quant-ph]. ^ 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. ^ Jump up to: a b 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.” ^ 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): 731–742. arXiv:1801.03821. Bibcode:2018arXiv180103821N. doi:10.1109/FOCS.2018.00075. ISBN 978-1-5386-4230-6. S2CID 53062680. ^ "On the NLTS Conjecture". Simons Institute for the Theory of Computing. 2021-06-30. Retrieved 2022-08-08. References Arora, Sanjeev; Lund, Carsten; Motwani, Rajeev; Sudan, Madhu; Szegedy, Mario (1998), "Proof verification and the hardness of approximation problems", Journal of the ACM, 45 (3): 501–555, doi:10.1145/278298.278306, S2CID 8561542. Arora, Sanjeev; Safra, Shmuel (1992), "Approximating clique is NP-complete", In Proceedings of the 33rd IEEE Symposium on Foundations on Computer Science, 41 (1): 2–13 Arora, Sanjeev; Safra, Shmuel (1998), "Probabilistic checking of proofs: A new characterization of NP", Journal of the ACM, 45 (1): 70–122, doi:10.1145/273865.273901, S2CID 751563. Babai, László; Fortnow, Lance; Levin, Leonid; Szegedy, Mario (1991), "Checking computations in polylogarithmic time", STOC '91: Proceedings of the twenty-third annual ACM symposium on Theory of computing, ACM, pp. 21–32, ISBN 978-0-89791-397-3. Babai, László; Fortnow, Lance; Lund, Carsten (1990), "Nondeterministic exponential time has two-prover interactive protocols", SFCS '90: Proceedings of the 31st Annual Symposium on Foundations of Computer Science, IEEE Computer Society, pp. 16–25, ISBN 978-0-8186-2082-9. Dinur, Irit (2007), "The PCP theorem by gap amplification", Journal of the ACM, 54 (3): 12–es, doi:10.1145/1236457.1236459, S2CID 53244523. Feige, Uriel; Goldwasser, Shafi; Lovász, László; Safra, Shmuel; Szegedy, Mario (1996), "Interactive proofs and the hardness of approximating cliques" (PDF), Journal of the ACM, ACM, 43 (2): 268–292, doi:10.1145/226643.226652, ISSN 0004-5411. Categories: Randomized algorithmsTheorems in computational complexity theory

Si quieres conocer otros artículos parecidos a PCP theorem puedes visitar la categoría Randomized algorithms.

Deja una respuesta

Tu dirección de correo electrónico no será publicada.

Subir

Utilizamos cookies propias y de terceros para mejorar la experiencia de usuario Más información