Report Number: CSL-TR-68-1
Institution: Stanford University, Computer Systems Laboratory
Title: On the computational complexity of finite functions
Author: Spira, Philip M.
Date: May 1968
Abstract: One of the most rapidly expanding fields of applied mathematics and engineering is automata theory. Although the term "automaton" is derived from "self-moving thing," the prime concern of automata theory is the study of information-processing devices. A specific example of information processing is computation, and thus the mathematical properties of devices which perform computations are of interest to automata theorists. In this thesis we investigate the computation by logic circuits of a certain class of functions having finite domain. To a given function f a number of so-called complexity criteria can be assigned relative to that class, e.g., the minimum computation time of or the minimum number of elements contained in any circuit of the class which is capable of computing f . Our prime criterion of interest will be computation time. The type of circuits investigated in this thesis are called (d,r ) circuits. A (d,r ) circuit is composed of logical elements each having at most r inputs and one output. Each input value and output value is an element from the set Z d = {0,1,...,d - 1}, and each element has unit delay in computing its output. Thus a given element computes a function from Z S(k,d) to Z d , for some k 2 r, in unit time. The output of one element can be connected to inputs of any number of elements (including itself) and can also comprise one of the outputs of the circuit and an element receives a given one of its inputs either from the output of some element or from the inputs to the circuit. When individual elements are interconnected to form a (d,r) circuit, we can associate a computation time with the entire circuit. Specifically, let f : X1,...,Xn . Y be any function on finite sets X1,...,Xn. Let C be a (d,r) circuit whose input lines are partitioned into n sets. Let IC,j be the set of configurations of values from Z d on the jth (J = 1,2,...,n) and let OC be the set of output configurations of the circuit. Then C is said to compute f in time t if there are maps gj : Xj . IC,j (j = 1,2,...,n) and a 1 - 1 function h : Y . OC such that, if the input from time 0 through time t - 1 is [g1(x1),...,gn(xn)], then the output of C at time t will be h(f(x1,...,xn)). Winograd has done pioneering work on the time of computation of finite functions by (d,r) circuits. He has derived lower bounds on computation time and has constructed near optimal circuits for many classes of finite functions. A principal contribution of this thesis is a complete determination of the time necessary to compute multiplication in a finite group with a (d,r) circuit. A new group theoretic quantity d(G) is defined whose reciprocal is the proper generalization of Winograd's a(G) to nonabelian groups. Then a novel method of circuit synthesis for group multiplication is given. In contrast to previous procedures, it is valid for any finite group--abelian or not. It is completely algebraic in character and is based upon our result that any finite group has a family of subgroups having a trivial intersection and minimum order d(G). The computation time achieved is, in all cases, at most one unit greater than our lower bound. In particular, if G is abelian our computation time is never greater--and often considerably less--than Winograd's. We then generalize the group multiplication procedure to a method to compute any finite function. For given sets X1, X2 and Y and any family of subsets of Y having a certain property called completeness, a corresponding hierarchy of functions having domain X1 x X2 and range Y is established -- the position of a function depending upon its computation time with our method. For reasons which we explain in the test, this appears to be a very natural classification criterion. At the bottom of the hierarchy are invertible functions such as numerical addition and multiplication, and the position of a function in the hierarchy depends essentially upon how far it is from being invertible. For large |X1| and |X2| almost all functions are near the top, corresponding to the fact that nearly all f : X1 x X2 . Y require computation time equal to the maximum required for any such function. The new method is then applied to the case of finite semigroup multiplication.
http://i.stanford.edu/pub/cstr/reports/csl/tr/68/1/CSL-TR-68-1.pdf