Uniformity (complexity)

The uniform complexity of a computational problem, is the complexity with respect to a computation model in which the same algorithm is used to solve the problem for all possible input lengths.

In a non-uniform models of computation inputs of different lengths are processed by different algorithms or computational devices (e.g. circuits or abstract machines), in contrast with uniform models such as Turing machines where the same computational device is used for all possible input lengths. An individual computational problem is thus associated with a particular family of computational devices $C_{1}$,$C_{2}$,... where each $C_{n}$ is the device handling inputs of n bits. A uniformity condition is often imposed on these families so that each individual device can be computed by some resource-bounded Turing machine.

References

• Vollmer, Heribert (1999). Introduction to Circuit Complexity: a Uniform Approach. Springer Verlag. ISBN 3-540-64310-9.

See also

• Circuit complexity