Class Description

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.

Linked From

P/log: P With Logarithmic Advice

Same as P/poly, except that the advice string for input size n can have length at most logarithmic in n, rather than polynomial.

Strictly contained in IC[log,poly].

If NP is contained in P/log then P = NP.

More about...

P/poly: Nonuniform Polynomial-Time

The class of decision problems solvable by a family of polynomial-size Boolean circuits. The family can be nonuniform; that is, there could be a completely different circuit for each input length.

Equivalently, P/poly is the class of decision problems solvable by a polynomial-time Turing machine that receives a trusted 'advice string,' that depends only on the size n of the input, and that itself has size upper-bounded by a polynomial in n.

Contains BPP by the progenitor of derandomization arguments [Adl78] [KL82]. By extension, BPP/poly, BPP/mpoly, and BPP/rpoly all equal P/poly. (By contrast, there is an oracle relative to which BPP/log does not equal BPP/mlog, while BPP/mlog and BPP/rlog are not equal relative to any oracle.)

[KL82] showed that, if P/poly contains NP, then PH collapses to the second level, Σ₂P.

They also showed:

• If PSPACE is in P/poly then PSPACE equals Σ₂P ∩ Π₂P.
• If EXP is in P/poly then EXP = Σ₂P.

It was later shown that, if NP is contained in P/poly, then PH collapses to ZPP^NP [KW98] and indeed to O₂P [CR06] (which is unconditionally included in P/poly). This seems close to optimal, since there exists an oracle relative to which the collapse cannot be improved to Δ₂P [Wil85].

If NP is not contained in P/poly, then P does not equal NP. Much of the effort toward separating P from NP is based on this observation. However, a 'natural proof' as defined by [RR97] cannot be used to show NP is outside P/poly, if there is any pseudorandom generator in P/poly that has hardness 2^{Ω(n^ε)} for some ε>0.

If NP is contained in P/poly, then MA = AM [AKS+95]

The monotone version of P/poly is mP/poly.

P/poly has measure 0 in E with Σ₂P oracle [May94b].

Strictly contains IC[log,poly] and P/log.

The complexity class of P with untrusted advice depending only on input size is ONP.

More about...