Introduction

The theory on efficient algorithms and complexity theory is software oriented. Their hardware-oriented counterpart is the theory on combinational circuits or, simply, circuits. The main difference is that circuits are a nonuniform model. A circuit is designed for one Boolean function f Є Bn,m, that is, f: {0, 1}n → {0, 1}m. However, most circuit designs lead to sequences of circuits realizing a sequence of functions. Typical adders are sequences of adders, one for each input length. If there is an efficient algorithm computing for each n the circuit for input length n, the circuit family is called uniform. However, for basic functions like arithmetic functions or storage access the circuit model is more adequate than software models. Moreover, circuits are a very simple and natural computation model reflecting all aspects of efficiency.

A circuit model needs a basis of elementary functions that can be realized by simple gates. In the basic circuitmodel, a basis is a finite set. Then a circuit for input size n is a finite sequence of instructions or gates and, therefore, a straight-line program: the ith instruction consists of a function g from the chosen basis and, if g Є Bj ≔ Bj,1, a sorted list Ii,1, …, Ii, j of inputs. The constants 0 and 1, the variables x1, …, xn, and the results r1, …, ri–1 of the first i – 1 instructions are possible inputs.