Section 6 - Circuit Complexity

CIRC.6.1 Circuit Complexity and Exponential Growth

An aribtrary boolean function that has N inputs requires, as we just saw, a list of 2^N booleans (the outputs for each possible input) to represent it, at least it would if we were to use the array representation just described. In other words, let's assume that we have a boolean function which we name f_N, where we appended the subscript N to indicate the number of input bits; it can handle inputs in the range, 0 to 2^N-1, and the table size for f_N would be 2^N. If we were to build a new function, "based somehow on f_N", but which took one extra bit, and called the new function f_N+1, the table size of the new function would, of course, have size 2^N+1, that is, it would require a table twice as large compared with the table of the original f_N.

Why do we care about this, and what does it even mean that f_N+1 was "somehow based" on the function f_N?

The answer lies in a field called decision theory. It turns out that a huge infinity of computational questions can be translated into a single (often large) boolean function with one ouput. Practically any computational problem you can think of asking can be expressed using a boolean function that solves it. The time it takes to solve the problem (the algorithm) corresponds to the size of the circuit (or table) that represents its boolean function.

The statement that "f_N+1 is somehow based on the function f_N" is a way to say that f_N represented the decision problem for an input of size N and f_N+1 represents that same decision problem for an input size one larger than N, or N+1. Both functions are related by virtue of their solving the same basic problem, but for different input sizes. Here, I'm using the letter f to label the decision problem at hand. If I had a different problem, I might use g (and the two tables for the different size inputs for this second problem, g_N and g_N+1).

As an example, the problem whose solution depends on N is

(The reason for picking the upper limit 2^N-1 is that we are asking whether k can be represented using N binary digits.) This question has a boolean function, f_N, that corresponds to the solution of the problem and a table that represents f_N . That function would answer the question for all inputs k <= 2^N-1; you supply any such k as an input, and the table would answer true if k were prime and false if not. In fact, for each N, we build a different boolean function that solves the prime number problem for all k < 2^N, so we get a function family, { f_N} dedicated to the prime number problem. As you can imagine, the algorithm takes more time to answer as N grows larger. This is also reflected in the table size for f_N which has has 2^N elements in it. Using such tables, { f_N}, the size of each f_N grows exponentially with N: each table is twice the size of the table before it. If we cannot find any better way to represent this algorithm other than to construct these brute-force tables then we say that the algorithm grows exponentially. For sake of argument, let's say we have not found a better way to answer this prime number question other than to supply the entire table of size 2^N. That would make the problem (potentially) one that exhibits exponential growth.

There are many circuits (and questions) that don't require a large table to represent them. For example, the question

can be answered by OR-ing the N bits that constitute k together. This is merely N-1 OR gates, and it grows linearly (like N) not exponentially (like 2^N). In other words, the boolean function family, { g_N}, that correspond to this question has a much slower growth rate than the family { f_N} that corresponds to the prime number question. So, some problems can be represented by a circuit that has a slower growth rate, others require circuits that grow exponentially.

The manner in which a problem's algorithm takes grows with N -- or the size that its family of functions {f_N} grows with N -- is called the complexity of the algorithm. Algorithms (function families) that have polynomial growth (grow like N or N² or N⁷) are labeled easy. Those that have exponential growth are called hard.

There are lots of ill-defined statements in this last section, all of which require several pages of math to make rigorous. They require us to define terms like deterministic and non-deterministic circuit families, and lead the famous P ≠ NP conjecture. That's for another course.

CIRC.6.2 Universal Gates

Just as we could represent the quesiton "is k (in the range 0 to 2^N-1) greatener than zero?" using (N-1) OR-gates, it turns out any arbitrary function f_N can be expressed using a circuit with a combination of relatively few binary or unary gates (like AND, OR, NOT, etc.) Whenever you have a small set of gates which can be used to build any boolean function, that set is called universal.

The gates AND, OR and NOT form one universal set. It's very easy to show this, although I won't do it here.

Can we do it in fewer gates? Yes. We only need one gate to build everything else: the NAND-gate (the not-and gate). We introduced ii in the previous page, but for reference, its defining table is:

You can do everything with this one gate. Furthermore, it isn't the only gate that can be used, without the help of other gates, to represent all boolean functions. (Think about it, or search for it online.)