The Library
Some results on circuit depth
Tools
Tools
Tools
McColl, William Finlay (1977) Some results on circuit depth. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
Research output not available from this repository, contact author.Abstract
An important problem in theoretical computer science is 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.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Functions, Computational complexity, Computers -- Circuits | ||||
| Series Name: | Theory of Computation Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | March 1977 | ||||
| Dates: |
|
||||
| Number: | Number 18 | ||||
| Number of Pages: | 135 | ||||
| DOI: | CS-RR-018 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Access rights to Published version: | Open Access | ||||
| Description: | See Related URL for option to download full text |
||||
| Funder: | Science Research Council (Great Britain) (SRC) | ||||
| Version or Related Resource: | McColl, W.F. (1977). Some results on circuit depth. Ph.D. thesis. University of Warwick | ||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
