This article includes a list ofgeneral references, butit lacks sufficient correspondinginline citations. Please help toimprove this article byintroducing more precise citations.(November 2012) (Learn how and when to remove this message)

Incomputational complexity theory, aprobabilistically checkable proof (PCP) is a type ofproof that can be checked by arandomized 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 (orcertificate), as used in theverifier-based definition of thecomplexity classNP, 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.

Probabilistically checkable proofs give rise to many complexity classes depending on the number of queries required and the amount of randomness used. The classPCP[r(n),q(n)] refers to the set ofdecision problems that have probabilistically checkable proofs that can be verified in polynomial time using at mostr(n) random bits and by reading at mostq(n) bits of the proof.^[1] Unless specified otherwise, correct proofs should always be accepted, and incorrect proofs should be rejected with probability greater than 1/2. ThePCP theorem, a major result in computational complexity theory, states thatPCP[O(logn),O(1)] =NP.

Given adecision problemL (or alanguage L with its alphabet set Σ), aprobabilistically checkable proof system forL with completenessc(n) and soundnesss(n), where0 ≤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 statesx solvesL (x ∈L, the proof is a string∈ Σ^∗). And the verifier is a randomizedoracle Turing MachineV (theverifier) that checks the proofπ for the statement thatx solvesL(orx ∈L) and decides whether to accept the statement. The system has the following properties:

• Completeness: For anyx ∈L, given the proofπ produced by the prover of the system, the verifier accepts the statement with probability at leastc(n),
• Soundness: For anyx ∉L, then for any proofπ, the verifier mistakenly accepts the statement with probability at mosts(n).

For thecomputational complexity of the verifier, the verifier is polynomial time, and we have therandomness complexityr(n) to measure the maximum number of random bits thatV uses over allx of lengthn and thequery complexityq(n) of the verifier is the maximum number of queries thatV makes to π over allx of lengthn.

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 benon-adaptive if it makes all its queries before it receives any of the answers to previous queries.

The complexity classPCP_c(n),s(n)[r(n),q(n)] is the class of all decision problems having probabilistically checkable proof systems over binary alphabet of completenessc(n) and soundnesss(n), where the verifier is non-adaptive, runs in polynomial time, and it has randomness complexityr(n) and query complexityq(n).

The shorthand notationPCP[r(n),q(n)] is sometimes used forPCP_{1, 1/2}[r(n),q(n)]. The complexity classPCP is defined asPCP_{1, 1/2}[O(logn),O(1)].

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 tocomputational complexity (in particularhardness of approximation) andcryptography.

The definition of a probabilistically checkable proof was explicitly introduced by Arora and Safra in 1992,^[2] although their properties were studied earlier. In 1990 Babai, Fortnow, and Lund proved thatPCP[poly(n), poly(n)] =NEXP, providing the first nontrivial equivalence between standard proofs (NEXP) and probabilistically checkable proofs.^[3] ThePCP theorem proved in 1992 states thatPCP[O(logn),O(1)] =NP.^[2][4]

The theory ofhardness of approximation requires a detailed understanding of the role of completeness, soundness, alphabet size, and query complexity in probabilistically checkable proofs.

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 standardcomplexity classes. For example, we have the following for different setting ofPCP[r(n),q(n)]:

• PCP[0, 0] =P (P is defined to have no randomness and no access to a proof.)
• PCP[O(logn), 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.)
• PCP[O(1),O(logn)] =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.)
• PCP[poly(n), 0] =coRP (By definition ofcoRP.)
• PCP[0, poly(n)] =NP (By the verifier-based definition ofNP.)

The PCP theorem andMIP = NEXP can be characterized as follows:

• PCP [O(logn),O(1)] =NP (the PCP theorem)
• PCP [poly(n),O(1)] =PCP [poly(n),poly(n)] =NEXP (MIP =NEXP).

Table of equalities

⁠${\displaystyle \mathsf{P}\mathsf{C}\mathsf{P}[r(n),q(n)]}$⁠	0	⁠${\displaystyle O(1)}$⁠	⁠${\displaystyle O(\log n)}$⁠	⁠${\displaystyle \mathrm{poly}(n)}$⁠
0	P	P	P	NP
⁠${\displaystyle O(1)}$⁠	P	P	P	NP
⁠${\displaystyle O(\log n)}$⁠	P	NP	NP	NP
⁠${\displaystyle \mathrm{poly}(n)}$⁠	coRP	MIP = NEXP	NEXP	NEXP

It is also known thatPCP[r(n),q(n)] ⊆NTIME(poly(n,2^O(r(n))q(n))). In particular,PCP[O(logn), poly(n)] =NP. On the other hand, ifNP ⊆PCP [o(logn),o(logn)] thenP = NP.^[2]

A Linear PCP is a PCP in which the proof is a vector of elements of a finite field${\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${\displaystyle q\in {\mathbb{F}}^n}$ is a linear function${\displaystyle f(q,\pi )}$. Linear PCPs have important applications in proof systems that can be compiled into SNARKs.

• Holographic proof at theEncyclopedia of Mathematics
• PCP course notes bySubhash Khot at theNew York University, 2008.
• PCP course notes andA history of the PCP theorem byRyan O'Donnell andVenkatesan Guruswami from theUniversity of Washington, 2005.
• Complexity Zoo:PCP

• Mathematical proofs
• Randomized algorithms

• Articles with short description
• Short description is different from Wikidata
• Articles lacking in-text citations from November 2012
• All articles lacking in-text citations