Complexity in Electronic Switching Circuits
David E. Muller · IRE Transactions on Electronic Computers · 1956
The complexity of an electronic switching circuit is defined in a sufficiently general way so that most definitions which are presently used may be included. If ø(p, q) is the complexity of a p input q output circuit which has been minimized then we may define E(p, q) as the maximum of ø(p, q) over all p input, q output circuits. In spite of the generality of the definition of complexity one may obtain the following inequality which gives upper and lower bounds on this maximum complexity: C12r/r≦E(p, q)≦C22r/r where r = p+log2q. In this expression C1and C2are constants independent of p and q which depend upon the definition of complexity. These theoretical bounds are compared with those obtained from a few known circuiit designs.