Probabilistically checkable proof

<h2 id="definition">Definition</h2>
Given a <a href="/facts/Computational_problem/jQ7bYUVh">decision problem</a> L (or a <a href="/facts/Formal_language/crDTyP8q">language</a> L with its alphabet set Σ), a probabilistically checkable proof system for L with completeness c(n) and soundness s(n), where 0 ≤ s(n) ≤ c(n) ≤ 1, consists of a prover and a verifier. Given a claimed solution x with length n, which might be false, the prover produces a proof π which states x solves L (x ∈ L, the proof is a string ∈ Σ∗). And the verifier is a randomized <a href="/facts/Oracle_machine/6ScMuvvY">oracle Turing Machine</a> V (the verifier) that checks the proof π for the statement that x solves L(or x ∈ L) and decides whether to accept the statement. The system has the following properties:

<ul><li>Completeness: For any x ∈ L, given the proof π produced by the prover of the system, the verifier accepts the statement with probability at least c(n),</li>
<li>Soundness: For any x ∉ L, then for any proof π, the verifier mistakenly accepts the statement with probability at most s(n).</li></ul>
For the <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> of the verifier, the verifier is polynomial time, and we have the randomness complexity r(n) to measure the maximum number of random bits that V uses over all x of length n and the query complexity q(n) of the verifier is the maximum number of queries that V makes to π over all x of length n.
In the above definition, the length of proof is not mentioned since usually it includes the alphabet set and all the witnesses. For the prover, we do not care how it arrives at the solution to the problem; we care only about the proof it gives of the solution's membership in the language.
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, runs in polynomial time, 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, 1/2[r(n), q(n)]. The complexity class PCP is defined as PCP1, 1/2[O(log n), O(1)].

<h2 id="history-and-significance">History and significance</h2>
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 <a href="/facts/Computational_complexity_theory/etHuVF3U">computational complexity</a> (in particular <a href="/facts/Hardness_of_approximation/YNKqhcej">hardness of approximation</a>) and <a href="/facts/Cryptography/e94PEVau">cryptography</a>.
The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992,<a class="footnote-ref" id="fnref:2" href="#fn:2">2</a> although their properties were studied earlier. In 1990 Babai, Fortnow, and Lund proved that PCP[poly(n), poly(n)] = <a href="/facts/NEXP/2pghWvBV">NEXP</a>, providing the first nontrivial equivalence between standard proofs (NEXP) and probabilistically checkable proofs.<a class="footnote-ref" id="fnref:3" href="#fn:3">3</a> The <a href="/facts/PCP_theorem/GwlBcYH6">PCP theorem</a> proved in 1992 states that PCP[O(log n),O(1)] = NP.<a class="footnote-ref" id="fnref:4" href="#fn:4">4</a><a class="footnote-ref" id="fnref:5" href="#fn:5">5</a>
The theory of <a href="/facts/Hardness_of_approximation/YNKqhcej">hardness of approximation</a> requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.

<h2 id="properties">Properties</h2>
From computational complexity point of view, for extreme settings of the parameters, the definition of probabilistically checkable proofs is easily seen to be equivalent to standard <a href="/facts/Complexity_classes/IIKrcTbP">complexity classes</a>. For example, we have the following for different setting of PCP[r(n), q(n)]:

<ul><li>PCP[0, 0] = P (<a href="/facts/P_(complexity)/2TYvck4k">P</a> is defined to have no randomness and no access to a proof.)</li>
<li>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.)</li>
<li>PCP[O(1),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 and constant-length random strings in polynomial time.)</li>
<li>PCP[poly(n), 0] = coRP (By definition of <a href="/facts/RP_(complexity)/KyYkqCHe">coRP</a>.)</li>
<li>PCP[0, poly(n)] = NP (By the verifier-based definition of <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>.)</li></ul>
The PCP theorem and <a href="/facts/Interactive_proof_system/rDB0agR9">MIP</a> = NEXP can be characterized as follows:

<ul><li>PCP [O(log n),O(1)] = NP (the PCP theorem)</li>
<li>PCP [poly(n),O(1)] = PCP [poly(n),poly(n)] = NEXP (MIP = NEXP).</li></ul>
Table of equalities<table><tbody><tr><th>⁠ P C P [ r ( n ) , q ( n ) ] {\displaystyle {\mathsf {PCP}}[r(n),q(n)]} ⁠</th><th>0</th><th>⁠ O ( 1 ) {\displaystyle O(1)} ⁠</th><th>⁠ O ( log ⁡ n ) {\displaystyle O(\log n)} ⁠</th><th>⁠ poly ⁡ ( n ) {\displaystyle \operatorname {poly} (n)} ⁠</th></tr><tr><td>0</td><td>P</td><td>P</td><td>P</td><td>NP</td></tr><tr><td>⁠ O ( 1 ) {\displaystyle O(1)} ⁠</td><td>P</td><td>P</td><td>P</td><td>NP</td></tr><tr><td>⁠ O ( log ⁡ n ) {\displaystyle O(\log n)} ⁠</td><td>P</td><td>NP</td><td>NP</td><td>NP</td></tr><tr><td>⁠ poly ⁡ ( n ) {\displaystyle \operatorname {poly} (n)} ⁠</td><td>coRP</td><td>MIP = NEXP</td><td>NEXP</td><td>NEXP</td></tr></tbody></table>
It is also known that PCP[r(n), q(n)] ⊆ <a href="/facts/NTIME/AqQII2Q8">NTIME</a>(poly(n,2O(r(n))q(n))). 
In particular, PCP[O(log n), poly(n)] = <a href="/facts/NP_(complexity)/6muUfVMI">NP</a>. 
On the other hand, if NP ⊆ PCP [o(log n),o(log n)] then <a href="/facts/P_%3D_NP/xoC7Ruda">P = NP</a>.<a class="footnote-ref" id="fnref:6" href="#fn:6">6</a>

<h2 id="linear-pcp">Linear PCP</h2>
A Linear PCP is a PCP in which the proof is a vector of elements of a finite field 
 
 
 
 π
 ∈
 
 
 F
 
 
 n
 
 
 
 
 {\displaystyle \pi \in \mathbb {F} ^{n}}
 
, and such that the PCP oracle is only allowed to do linear operations on the proof. Namely, the response from the oracle to a verifier query 
 
 
 
 q
 ∈
 
 
 F
 
 
 n
 
 
 
 
 {\displaystyle q\in \mathbb {F} ^{n}}
 
 is a linear function 
 
 
 
 f
 (
 q
 ,
 π
 )
 
 
 {\displaystyle f(q,\pi )}
 
. Linear PCPs have important applications in proof systems that can be compiled into SNARKs.

<h2 id="external-links">External links</h2>
<ul><li><a href="https://encyclopediaofmath.org/wiki/Holographic_proof">Holographic proof</a> at the <a href="/facts/Encyclopedia_of_Mathematics/WC6mGtPm">Encyclopedia of Mathematics</a></li>
<li><a href="http://www.cs.nyu.edu/~khot/pcp-course.html">PCP course notes</a> by <a href="/facts/Subhash_Khot/rQ852PWC">Subhash Khot</a> at the <a href="/facts/New_York_University/4UnIkThy">New York University</a>, 2008.</li>
<li><a href="https://courses.cs.washington.edu/courses/cse533/05au/">PCP course notes</a> and <a href="https://courses.cs.washington.edu/courses/cse533/05au/pcp-history.pdf">A history of the PCP theorem</a> by <a href="/facts/Ryan_O%27Donnell_(computer_scientist)/Y2F0eoLe">Ryan O'Donnell</a> and <a href="/facts/Venkatesan_Guruswami/FLUy7glV">Venkatesan Guruswami</a> from the <a href="/facts/University_of_Washington/36PG6qkG">University of Washington</a>, 2005.</li>
<li><a href="/facts/Complexity_Zoo/htGK5zuz">Complexity Zoo</a>: <a href="https://complexityzoo.net/Complexity_Zoo:P#pcp">PCP</a></li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1">Arora, Sanjeev; Barak, Boaz (2007), Computational Complexity: A Modern Approach, Cambridge University Press, p. 241, ISBN 978-0-521-42426-4 <a href="978-0-521-42426-4" target="_blank">978-0-521-42426-4</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></li>
<li id="fn:2">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 <a href="/wiki/Sanjeev_Arora" target="_blank">/wiki/Sanjeev_Arora</a> <a href="#fnref:2" class="footnote-back-ref">↩</a></li>
<li id="fn:3">Babai, László; Fortnow, Lance; Lund, Carsten (1990), "Nondeterministic exponential time has two-prover interactive protocols", Proceedings of the 31st Annual Symposium on Foundations of Computer Science (FOCS 1990), pp. 16–25, CiteSeerX 10.1.1.130.9311, doi:10.1109/FSCS.1990.89520, ISBN 978-0-8186-2082-9, S2CID 38429596 <a href="978-0-8186-2082-9" target="_blank">978-0-8186-2082-9</a> <a href="#fnref:3" class="footnote-back-ref">↩</a></li>
<li id="fn:4">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 <a href="/wiki/Sanjeev_Arora" target="_blank">/wiki/Sanjeev_Arora</a> <a href="#fnref:4" class="footnote-back-ref">↩</a></li>
<li id="fn:5">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 <a href="/wiki/Sanjeev_Arora" target="_blank">/wiki/Sanjeev_Arora</a> <a href="#fnref:5" class="footnote-back-ref">↩</a></li>
<li id="fn:6">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 <a href="/wiki/Sanjeev_Arora" target="_blank">/wiki/Sanjeev_Arora</a> <a href="#fnref:6" class="footnote-back-ref">↩</a></li>
</ol>

Probabilistically checkable proof open-in-new

Probabilistically checkable proof