Complexity in Electronic Switching Circuits

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: C 1 2 r /r≦E(p, q)≦C 2 2 r /r where r = p+log 2 q. In this expression C 1 and C 2 are 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.