Complexity Zoo:I
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 - IOP - 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 Proof Systems
The class of decision problems for which a "yes" answer can be verified by an interactive proof. Here a 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.
Defined in [GMR89], with the motivation of providing a framework for the introduction of zero-knowledge proofs (see the class ZK). Interestingly, the power of general interactive proof systems is not decreased if the verifier is only allowed random queries (i.e., it merely tosses coins and sends any outcome to the prover). The latter model, known as the Arthur-Merlin (or public-coin) model was introduced independently (but later) in [Bab85], and a strong equivalent (which preserves the number of rounds) is proved in [GS86]. Often, it is required that the prover can convince the verifier to accept correct assertions with probability 1; this is called perfect completeness. However, the definitions with one-sided and two-sided error can be shown to be equivalent (see [FGM+89]).
First demonstration to the power of interactive proofs was given by showing that for graph nonisomorphism (a problem not known in NP) has such proofs [GMW91]. Five years later is was shown that IP contains PH [LFK+90], and indeed (this was discovered only a few weeks later) equals PSPACE [Sha90]. On the other hand, coNP is not contained in IP relative to a random oracle [CCG+94]. See also: MIP, QIP, MA, AM.
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).
See also: PPSPACE.
IP[polylog]:
- Alternate name for AM[polylog].