Properties
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:
- PCP = P (P is defined to have no randomness and no access to a proof.)
- PCP = 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 = 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 in polynomial time.)
- PCP = coRP (By definition of coRP.)
- PCP = NP (By the verifier-based definition of NP.)
The PCP theorem and MIP = NEXP can be characterized as follows:
- PCP = NP (the PCP theorem)
- PCP = PCP = NEXP (MIP = NEXP).
It is also known that PCP ⊆ NTIME(2O(r(n))q(n)+poly(n)), if the verifier is constrained to be non-adaptive. For adaptive verifiers, PCP ⊆ NTIME(2O(r(n)+q(n))+poly(n)). On the other hand, if NP ⊆ PCP then P = NP.
Read more about this topic: Probabilistically Checkable Proof
Famous quotes containing the word properties:
“A drop of water has the properties of the sea, but cannot exhibit a storm. There is beauty of a concert, as well as of a flute; strength of a host, as well as of a hero.”
—Ralph Waldo Emerson (1803–1882)
“The reason why men enter into society, is the preservation of their property; and the end why they choose and authorize a legislative, is, that there may be laws made, and rules set, as guards and fences to the properties of all the members of the society: to limit the power, and moderate the dominion, of every part and member of the society.”
—John Locke (1632–1704)