Complexity Zoo:I

From Qwiki

Back to the Main Zoo - Complexity Garden - Zoo Glossary - Zoo References

Complexity classes by letter: Symbols - A - B - C - D - E - F - G - H - I - J - K - L - M - N - O - P - Q - R - S - T - U - V - W - X - Y - Z

Lists of related classes: Communication Complexity - Hierarchies - Nonuniform

IC[log,poly] - IP - IPP - IP[polylog]

IC[log,poly]: 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:

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|).
Whenever A returns "yes" or "no", it is correct.
A returns either "yes" or "no" on x.

Defined in [OKS+94]; see also [LV97].

If NP is contained in IC[log,poly], then P = NP [OKS+94]. Indeed, any self-reducible problem in IC[log,poly] is also in P.

Strictly contains P/log, and is strictly contained in P/poly.

IP: Interactive Polynomial Time

The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a 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:

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).
If the answer is "no," then however the prover behaves the verifier must reject with probability at least 2/3.

IP contains PH [LFK+90], and indeed (this was discovered only a few days later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94].

IPP: Unbounded IP

Same as 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 [CCG+94], where it was also shown that IPP = PSPACE relative to all oracles. Since IP is strictly contained in 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).