Editing Probabilistically checkable proof (section)

== Definition ==
Given a [[Computational_problem#Decision_problem|decision problem]] ''L'' (or a [[Formal_language|language]] L with its alphabet set Σ), a '''probabilistically checkable proof system''' for ''L'' with  completeness ''c''(''n'') and soundness ''s''(''n''), where {{math|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 {{mvar|L}} ({{math|''x'' ∈ ''L''}}, the proof is a string {{math|∈ Σ<sup>&lowast;</sup>}}). And the verifier is a randomized [[oracle machine|oracle Turing Machine]] ''V'' (the ''verifier'') that checks the proof ''π'' for the statement that ''x'' solves {{mvar|L}}(or {{math|''x'' ∈ ''L''}}) and decides whether to accept the statement. The system has the following properties:
* '''Completeness''': For any {{math|''x'' ∈ ''L''}}, given the proof ''π'' produced by the prover of the system, the verifier accepts the statement with probability at least ''c''(''n''),
* '''Soundness''': For any {{math|''x'' ∉ ''L''}}, then for any proof ''π'', the verifier mistakenly accepts the statement with probability at most ''s''(''n'').

For the [[Computational complexity theory|computational complexity]] 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 {{math|{{sans-serif|PCP}}<sub>''c''(''n''), ''s''(''n'')</sub>[''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 non-adaptive, runs in polynomial time, and it has randomness complexity ''r''(''n'') and query complexity ''q''(''n'').

The shorthand notation {{math|{{sans-serif|PCP}}[''r''(''n''), ''q''(''n'')]}} is sometimes used for {{math|{{sans-serif|PCP}}<sub>1, 1/2</sub>[''r''(''n''), ''q''(''n'')]}}.  The complexity class '''PCP''' is defined as {{math|{{sans-serif|PCP}}<sub>1, 1/2</sub>[''O''(log ''n''), ''O''(1)]}}.