Complexity Zoo:List of Nonuniform Classes
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
Nonuniformity allows for the use of a different algorithm for each input length considered. For example, if the Boolean circuit to decide a language was a function of the input length, then we would say that the family of circuits was nonuniform. An alternate characterization of nonuniformity concerns giving a Turing machine advice dependent on the input length. Though one can often just add nonuniformity to a class as a part of its description, we list here those nonuniform versions of classes about which something non-trivial has been shown.
#L/poly - ⊕L/poly - BPP/log - BPP/mlog - BPP//log - BPP/rlog - BQP/log - BQP/poly - BQP/mlog - BQP/mpoly - BQP/qlog - BQP/qpoly - BQPtt/poly - coNP/poly - EXP/poly - FNL/poly - L/poly - mP/poly - NE/poly - NEXP/poly - NL/poly - NP/log - NP/poly - (NP ∩ coNP)/poly - P/log - P/poly - PP/poly - PSPACE/poly - QMA/qpoly - UL/poly