Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

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.

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: 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:
DateEvent
March 1977["eprint_fieldopt_dates_date_type_available" not defined]
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:
  • Related item in WRAP

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item
twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us