The Library
Circuit size is nonlinear in depth
Tools
Tools
Tools
Valiant, Leslie and Paterson, Michael S. (1975) Circuit size is nonlinear in depth. University of Warwick. Department of Computer Science. (Theory of Computation Report). (Unpublished)
|
Text
WRAP_Valiant_cs-rr-008.pdf - Published Version Download (386Kb) | Preview |
Abstract
Two fundamental complexity measures for a Boolean function f are its circuit depth d(f) and its circuit size c(f). It is shown that c >=1/4 d.log2d for all f.
| Item Type: | Report | ||||
|---|---|---|---|---|---|
| Subjects: | Q Science > QA Mathematics | ||||
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||
| Library of Congress Subject Headings (LCSH): | Functions, Computational complexity | ||||
| Series Name: | Theory of Computation Report | ||||
| Publisher: | University of Warwick. Department of Computer Science | ||||
| Official Date: | September 1975 | ||||
| Dates: |
|
||||
| Number: | Number 8 | ||||
| Number of Pages: | 5 | ||||
| DOI: | CS-RR-008 | ||||
| Institution: | University of Warwick | ||||
| Theses Department: | Department of Computer Science | ||||
| Status: | Not Peer Reviewed | ||||
| Publication Status: | Unpublished | ||||
| Reuse Statement (publisher, data, author rights): | L.G. Valiant and M.S. Paterson, Circuit Size is Nonlinear in Depth, Theoretical Computer Science 2 (3), pp. 397-400 (1976) | ||||
| Access rights to Published version: | Open Access (Creative Commons) | ||||
| Date of first compliant deposit: | 1 August 2016 | ||||
| Date of first compliant Open Access: | 1 August 2016 | ||||
| Version or Related Resource: | Valiant, L.G. and Paterson, M.S. (1976). Circuit size is nonlinear in depth. Theoretical Computer Science, 2(3), pp. 397-400. |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
