Difference between revisions of "Complexity Zoo:List of Nonuniform Classes"
m (1 revision: Complexity zoo import.)
Revision as of 03:10, 18 November 2012
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 - NL/poly - NP/log - P/log - P/poly - PP/poly - PSPACE/poly - QMA/qpoly