View source

From Qwiki

You do not have permission to do that, for the following reason:

The action you have requested is limited to users in one of the groups user, zoo.

You can view and copy the source of this page:

__NOTOC__
{{CZ-Letter-Menu|I}}


===== <span id="iclogpoly" style="color:red">IC[log,poly]</span>: Logarithmic Instance Complexity, Polynomial Time =====
The class of decision problems such that, for every n-bit string x, there exists a program A of size O(log n) that, given x as input, "correctly decides" the answer on x in time polynomial in n.  This means:
<ul>
<li>There exists a polynomial p such that for any input y, A returns either "yes", "no", or "I don't know" in time p(|y|).</li>
<li>Whenever A returns "yes" or "no", it is correct.</li>
<li>A returns either "yes" or "no" on x.</li>
</ul>
Defined in [[zooref#oks94|[OKS+94]]]; see also [[zooref#lv97|[LV97]]].

If [[Complexity Zoo:N#np|NP]] is contained in IC[log,poly], then [[Complexity Zoo:P#p|P]] = [[Complexity Zoo:N#np|NP]] [[zooref#oks94|[OKS+94]]].  Indeed, any self-reducible problem in IC[log,poly] is also in [[Complexity Zoo:P#p|P]].

Strictly contains [[Complexity Zoo:P#plog|P/log]], and is strictly contained in [[Complexity Zoo:P#ppoly|P/poly]].

----
===== <span id="ip" style="color:red">IP</span>: Interactive Polynomial Time =====
The class of decision problems for which a "yes" answer can be verified by an <i>interactive proof</i>.  Here a [[Complexity Zoo:B#bpp|BPP]] (i.e. probabilistic polynomial-time) verifier sends messages back and forth with an all-powerful prover.  They can have polynomially many rounds of interaction. Given the verifier's algorithm, at the end:
<ol>
<li>If the answer is "yes," the prover must be able to behave in such a way that the verifier accepts with probability at least 2/3 (over the choice of the verifier's random bits).</li>
<li>If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.</li>
</ol>
IP contains [[Complexity Zoo:P#ph|PH]] [[zooref#lfk90|[LFK+90]]], and indeed (this was discovered only a few days later) equals [[Complexity Zoo:P#pspace|PSPACE]] [[zooref#sha90|[Sha90]]].  On the other hand, [[Complexity Zoo:C#conp|coNP]] is not contained in IP relative to a random oracle [[zooref#ccg94|[CCG+94]]].

See also: [[Complexity Zoo:M#mip|MIP]], [[Complexity Zoo:Q#qip|QIP]], [[Complexity Zoo:M#ma|MA]], [[Complexity Zoo:A#am|AM]].

----

===== <span id="ipp" style="color:red">IPP</span>: Unbounded [[#ip|IP]] =====
Same as [[#ip|IP]], except that if the answer is "yes," there need only be a prover strategy that causes the verifier to accept with probability greater than 1/2, while if the answer is "no," then for all prover strategies the verifier accepts with probability less than 1/2.

Defined in [[zooref#ccg94|[CCG+94]]], where it was also shown that IPP = [[Complexity Zoo:P#pspace|PSPACE]] relative to <i>all</i> oracles.  Since [[#ip|IP]] is strictly contained in [[Complexity Zoo:P#pspace|PSPACE]] relative to a random oracle, the authors interpreted this as evidence against the Random Oracle Hypothesis (a slight change in definition can cause the behavior of a class relative to a random oracle to change drastically).

See also: [[Complexity Zoo:P#ppspace|PPSPACE]].

----
===== <span id="ippolylog" style="color:red">IP[polylog]</span>: Alternate Name for [[Complexity Zoo:A#ampolylog|AM[polylog]]] =====

Templates used on this page:

Return to Complexity Zoo:I.

Retrieved from "http://qwiki.stanford.edu/wiki/Complexity_Zoo:I"

View source

From Qwiki

Views

Personal tools

Navigation

Search

Toolbox