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 > 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 |
| Date: | September 1975 |
| Number: | Number 8 |
| Number of Pages: | 5 |
| Identification Number: | CS-RR-008 |
| Institution: | University of Warwick |
| Theses Department: | Department of Computer Science |
| Status: | Not Peer Reviewed |
| Publication Status: | Unpublished |
| Access rights to Published version: | Open Access |
| 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. |
| URI: | http://wrap.warwick.ac.uk/id/eprint/46306 |
Actions (login required)
 |
View Item |
