Introduction to Circuit Complexity

Suppose we are given two binary strings, each consisting of n bits, a = a _n−1 a _n−2 ... a ₀, and b = b _n−1 b _n−2 ... b ₀. We want to solve the following problem: Interpret a and b as binary representations of two natural numbers and compute their sum (again in binary). We refer to this problem as ADD.

The results of the previous chapter show that there is a circuit complexity class which contains every length-respecting function f : {0,1}* → {0,1}*, computable or not:

The computational model of Boolean circuits attracted much interest among complexity theorists since it is a model where non-trivial lower bounds for specific functions are known. We treat this topic in the present chapter, but we want to stress that we present only very few out of a large and still-growing body of results. The interested reader will find references at the end of the chapter.

In this chapter we want to examine a class which has turned out to be of immense importance in the theory of efficient parallel algorithms. What should be considered to be a “good” parallel algorithm? First the number of processors should certainly not be too high, i. e., still polynomial in the input length. Second, the algorithm should achieve a considerable speed-up compared to efficient sequential algorithms, which typically run in polynomial time for a polynomial of small degree. These requirements led researchers to consider the class NC of all problems for which there are circuit families that are simultaneously of polynomial size and polylogarithmic (i.e., (log n) ^{o (1)}) depth. By the results presented in Sect. 2.7 this corresponds to polynomial processor number and polylogarithmic time on parallel random access machines. NC is the class of problems solvable with very fast parallel algorithms using a reasonable amount of hardware.

Arithmetic circuits are circuits whose gates compute operations over a semi-ring instead of the usual Boolean connectives (more precisely: operations over a semi-ring other than the Boolean semi-ring). The theory of arithmetic circuits, a very rich field with strong upper and lower bounds on the complexity of practical computational problems, serves as a theoretical basis for computer algebra and algebraic computations in symbolic computation software packages.

In the previous chapters we studied mostly subclasses of the class NC. As we have stressed already, NC is meant to stand for problems with feasible highly parallel solutions (meaning very efficient runtime using a reasonable number of processors). In the theory of sequential algorithms, the class P = DTIME(n ^{O (1)}) is meant to capture the notion of problems with feasible sequential algorithms (meaning reasonable runtime on a sequential machine). Every feasible highly parallel solution can be used to obtain a feasible sequential solution (NC ⊆ P). The question whether every problem with a feasible sequential algorithm also has a feasible parallel algorithm was discussed in detail in Sect. 4.6.