Class Description

NL/poly: Nonuniform NL

Has the same relation to NL as P/poly does to P.

Is contained in ⊕L/poly [GW96], as well as SAC1.

Equals UL/poly [RA00].

Linked From

⊕L/poly: Nonuniform ⊕L

Has the same relation to ⊕L as P/poly does to P.

Contains NL/poly [GW96].

More about...


UL/poly: Nonuniform UL

Has the same relation to UL as P/poly does to P.

Equals NL/poly [RA00]. (A corollary is that UL/poly is closed under complement).

Note that in UL/poly, the witness must be unique even for bad advice. UL/mpoly (as in BQP/mpoly) is a more natural definition, but this is a moot distinction here because [RA00] show that they both equal NL/poly.

More about...