Some results on circuit depth

[thumbnail of WRAP_THESIS_McColl_1977.pdf]
Preview
 Text
WRAP_THESIS_McColl_1977.pdf - Submitted Version
Download (3MB) | Preview

Request Changes to record.

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: Thesis [via Doctoral College] (PhD)
Subjects: Q Science > QA Mathematics
Library of Congress Subject Headings (LCSH): Functions, Computational complexity, Computers -- Circuits
Official Date: October 1976
Dates:
Date
Event
October 1976
Submitted
Institution: University of Warwick
Theses Department: Department of Computer Science
Thesis Type: PhD
Publication Status: Unpublished
Supervisor(s)/Advisor: Paterson, Michael S.
Sponsors: Science Research Council (Great Britain) (SRC)
Extent: i, 135 leaves
Language: eng
Related URLs:
URI: https://wrap.warwick.ac.uk/59627/

Export / Share Citation


Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item