Class Description

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.

Linked From

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:

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.

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, Σ2P.

They also showed:

It was later shown that, if NP is contained in P/poly, then PH collapses to ZPPNP [KW98] and indeed to O2P [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 Δ2P [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 Σ2P 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...