nonuniform complexity

in contrast to the standard (or uniform) TM model where the same TM is used on all the infinitely many input sizes, a nonuniform model allows a different algorithm to be used for each input size.
[cite:;taken2 from @computability_arora_2009 chapter 6 boolean circuits]

let $\text{[math]}$ be a class of sets. let $\text{[math]}$ be a class of functions from $\text{[math]}$ . the class $\text{[math]}$ is defined to consist of all sets $\text{[math]}$ for which there exist a set $\text{[math]}$ and a function $\text{[math]}$ such that for all $\text{[math]}$ ,
$\text{[math]}$ [cite:;taken2 from @complexity_vollmer_1999 definition 2.11]

$\text{[math]}$ is a so-called non-uniform complexity class. in the notation in the definition, the function $\text{[math]}$ gives, depending on the length of the actual input $\text{[math]}$ , additional information to the set $\text{[math]}$ (or a machine deciding $\text{[math]}$ ). therefore, $\text{[math]}$ is called an advice function, and $\text{[math]}$ is the advice for inputs of length $\text{[math]}$ . $\text{[math]}$ is also called an advice class.

let $\text{[math]}$ . then $\text{[math]}$ . if $\text{[math]}$ is a class of functions then $\text{[math]}$ . set $\text{[math]}$ , i.e., the set of all polynomially length-bounded functions.
[cite:;taken2 from @complexity_vollmer_1999 definition 2.12]

there are non-recursive languages in $\text{[math]}$ .
[cite:;taken2 from @complexity_vollmer_1999 chapter 2.3 non-uniform turing machines]

let $\text{[math]}$ . an $\text{[math]}$ advice sequence is a sequence of binary strings $\text{[math]}$ , where $\text{[math]}$ . for a language $\text{[math]}$ * let $\text{[math]}$ . let $\text{[math]}$ . let $\text{[math]}$ . apply this notation to other complexity classes, e.g., $\text{[math]}$ . these classes are sometimes referred to as "nonuniform P" or "nonuniform NP".
[cite:;taken2 from @tcs_leeuwen_1990 chapter 14 definition 2.2]

$\text{[math]}$ is defined similarly to ppoly but for $\text{[math]}$ (nonuniform_complexity.html).

there is a way to make the circuit model of computation a uniform one: we restrict the families of circuits to those which can be output by a Turing Machine. so we obtain an alternative characterization of $\text{[math]}$ :

$\text{[math]}$ .

we can also make the usual turing machine model of computation non-uniform. to do this, we give it a polynomially sized advice string which depends only on the length of the input. there is no constraint on what kind of function this advice can be; if we wish, it could even be undecidable.

the class of languages decided by turing machines equipped with an advice string is equivalent to $\text{[math]}$ .