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:
“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)
“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)