Canonical Form For Logic Gates As Shallow Architectures With Large Space Computational Complexities
A two-layer circuit of logic gates can represent any Boolean function (127). Any Boolean function can be written as a sum of products (disjunctive normal form: AND gates on the first layer with optional negation of inputs, and OR gate on the second layer) or a product of sums (conjunctive normal form: OR gates on the first layer with optional negation of inputs, and AND gate on the second layer). To understand the limitations of shallow architectures, the first result to consider is that with depth-two logical circuits, most Boolean functions require an exponential (with respect to input size) number of logic gates (198) to be represented.
More interestingly, there are functions computable with a polynomial-size logic gates circuit of depth k that require exponential size when restricted to depth k − 1 (62). The proof of this theorem relies on earlier results (208) showing that d-bit parity circuits of depth 2 have exponential size. The d-bit parity function is defined as usual:
(62) J. Håstad, “Almost optimal lower bounds for small depth circuits,” in Proceedings of the 18th annual ACM Symposium on Theory of Computing, pp. 6–20, Berkeley, California: ACM Press, 1986.
(127) E. Mendelson, Introduction to Mathematical Logic, 4th ed. 1997. Chapman & Hall.
(198) I. Wegener, The Complexity of Boolean Functions. John Wiley & Sons, 1987.
(208) A. Yao, “Separating the polynomial-time hierarchy by oracles,” in Proceedings of the 26th Annual IEEE Symposium on Foundations of Computer Science, pp. 1–10, 1985.
Quoted on Sun Dec 2nd, 2012