McColl, W. F. (1977) Some results on circuit depth. Coventry, UK: Department of Computer Science..

Full text not available from this repository.

Abstract

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.

Item Type:	Report
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
Date:	March 1977
Identification Number:	CS-RR-018
Institution:	University of Warwick
Theses Department:	Department of Computer Science
Status:	Not Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
Related URLs:	Other Repository
URI:	http://wrap.warwick.ac.uk/id/eprint/46318

Request changes to a record

Actions (login required)

View Item