Editing Probabilistically checkable proof (section)

== Properties ==
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 [[complexity classes]].  For example, we have the following for different setting of {{math|1={{sans-serif|PCP}}[''r''(''n''), ''q''(''n'')]}}:
* {{math|1={{sans-serif|PCP}}[0, 0] = {{sans-serif|P}}}} ({{sans-serif|[[P (complexity)|P]]}} is defined to have no randomness and no access to a proof.)
* {{math|1={{sans-serif|PCP}}[''O''(log ''n''), 0] = {{sans-serif|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.)
* {{math|1={{sans-serif|PCP}}[O(1),''O''(log ''n'')] = {{sans-serif|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.)
* {{math|1={{sans-serif|PCP}}[poly(''n''), 0] = {{sans-serif|coRP}}}} (By definition of {{sans-serif|[[RP (complexity)|coRP]]}}.)
* {{math|1={{sans-serif|PCP}}[0, poly(''n'')] = {{sans-serif|NP}}}} (By the verifier-based definition of {{sans-serif|[[NP (complexity)|NP]]}}.)

The PCP theorem and [[Interactive proof system#MIP|MIP]] = NEXP can be characterized as follows:
*{{math|1={{sans-serif|PCP}} [''O''(log ''n''),''O''(1)] = {{sans-serif|NP}}}}  (the PCP theorem)
*{{math|1={{sans-serif|PCP}} [poly(''n''),''O''(1)] = {{sans-serif|PCP}} [poly(''n''),poly(''n'')] = {{sans-serif|NEXP}}  ({{sans-serif|MIP}} = {{sans-serif|NEXP}})}}.
{| class="wikitable"
|+Table of equalities
!{{tmath|\mathsf{PCP}[r(n), q(n)]}}
!0
!{{tmath|O(1)}}
!{{tmath|O(\log n)}}
!{{tmath|\operatorname{poly}(n)}}
|-
|0
|P
|P
|P
|NP
|-
|{{tmath|O(1)}}
|P
|P
|P
|NP
|-
|{{tmath|O(\log n)}}
|P
|NP
|NP 
|NP
|-
|{{tmath|\operatorname{poly}(n)}}
|coRP
|MIP = NEXP
|NEXP
|NEXP
|}
It is also known that {{math|1={{sans-serif|PCP}}[''r''(''n''), ''q''(''n'')] ⊆ {{sans-serif|[[NTIME]]}}(poly(''n'',2<sup>''O''(''r''(''n''))</sup>''q''(''n'')))}}.  
In particular, {{math|1={{sans-serif|PCP}}[O(log ''n''), poly(''n'')] = {{sans-serif|[[NP (complexity)|NP]]}}}}. 
On the other hand, if {{math|{{sans-serif|NP}} ⊆ {{sans-serif|PCP }} [''o''(log ''n''),''o''(log ''n'')]}} then [[P = NP]].{{r|as92}}