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].

The verifier for PSPACE only uses logarithmic space when given two way, read only access to its randomness. On the other hand, given only read once access to its randomness, a log space verifier can only verify languages in P [Sha90]. Further, a log space verifier with read once access to its randomness can verifier any language in P [GKR15]. See BPL vs BP•L for a comparison between read once and read multiple access to randomness.

IOP: Interactive Oracle Proof

An interactive oracle proof (IOP) is a proof system that combines PCP and IP. An IOP allows both the prover and verifier to send messages like in the interactive proof model, but the verifier is given oracle access to the prover's messages. This is similar to a PCP, but instead of sending one fixed proof, the prover can send multiple proofs during the interaction, with the proofs' contents depending on the verifier messages. The verifier can then randomly query symbols from the received proofs.

The class of problems solved by IOP is NEXP, which is also the class of problems solved by PCP. Therefore IOPs are not more powerful than PCPs, but they can achieve better parameters such as total proof length, alphabet size, and query complexity. The parameters of an IOP are determined by simply summing up the parameters at each round. IOPs can be converted to IPs using Merkle trees via the BCS compiler, the same way PCPs are converted.

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).

IP[polylog]:

Alternate name for AM[polylog].