Information Theory and the Complexity of Switching Networks

Authors

Nicholas J. Pippenger, Harvey Mudd CollegeFollow

Document Type

Conference Proceeding

Department

Mathematics (HMC)

Publication Date

10-1975

Abstract

Our purpose in this paper is to establish some relationships between two areas pioneered by Shannon: information theory and the complexity of switching networks that realize Boolean functions. We investigate the following three questions.

1. How does the complexity of a function depend on the number of 1's and 0's in its truth table?

2. How does the complexity of an incompletely specified function depend on the number of unspecified entries in its truth table?

3. If we do not insist that a function be realized exactly, but allow a certain number of entries in its truth table to be changed, what reduction in complexity is possible?

These questions are answered by combinatorial arguments, but in each case the answer admits an information-theoretic interpretation that renders it more memorable. This interpretation has only heuristic significance, however, and does not provide an alternate means of deriving our results.

Rights Information

© 1975 IEEE

DOI

10.1109/SFCS.1975.18

Recommended Citation

Pippenger, Nicholas. "Information Theory and the Complexity of Switching Networks", IEEE Symp. on Foundations of Comp. Sci., 16 (1975), 113-118.