1.Previous
3.Next

of probabilistically checkable proofs is easily seen to be equivalent to standard complexity classes. For example, we have the following for different setting of :
* ( is defined to have no randomness and no access to a proof.)
* (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.)
* (Without randomness, the proof can be thought of as a fixed logarithmic sized string.

1.Previous
3.Next