Some results on circuit depth
McColl, W. F. (1977) Some results on circuit depth. Coventry, UK: Department of Computer Science..Full text not available from this repository.
Official URL: http://eprints.dcs.warwick.ac.uk/1141/1/cs-rr-018....
An important problem in theoretical computer science ls to develop methods for estimating the complexity of finite functions. For many familiar functions there remain important gaps between the best known lower and upper bound we investigate the inherent complexity of Boolean functional taking circuits as our model of computation and depth (or delay)to be the measure of complexity. The relevance of circuits as a model of computation for Boolean functions stems from the fact that Turing machine computations may be efficiently simulated by circuits. Important relations among various measures of circuit complexity are btained as well as bounds on the maximum depth of any function and of any monotone function. We then give a detailed account of the complexity of NAND circuits for several important functions and pursue an analysis of the important set of symmetric functions. A number of gap theorems for symmetric functions are exhibited and these are contrasted with uniform hierarchies for several large sets of functions. Finally, we describe several short formulae for threshold functions.
|Subjects:||Q Science > QA Mathematics > QA75 (Please use QA76 Electronic Computers. Computer Science)|
|Divisions:||Faculty of Science > Computer Science|
|Publisher:||Department of Computer Science|
|Place of Publication:||Coventry, UK|
|Institution:||University of Warwick|
|Theses Department:||Department of Computer Science|
|Status:||Not Peer Reviewed|
|Access rights to Published version:||Open Access|
Actions (login required)