ON THE COMPUTATIONAL COMPLEXITY OF FINITE FUNCTIONS.
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. (Author)
Document Details
- Document Type
- Technical Report
- Publication Date
- May 01, 1968
- Accession Number
- AD0696085
Entities
People
- Philip M. Spira
Organizations
- Stanford University