The Library
Circuit size is nonlinear in depth
Tools
Tools
Tools
Valiant, L. G. and Paterson, Michael S. (1975) Circuit size is nonlinear in depth. Coventry, UK: Department of Computer Science..
Full text not available from this repository.
Official URL: http://eprints.dcs.warwick.ac.uk/1131/1/cs-rr-008....
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\geq \frac{1}{4}d.log_2 d $ for all $f$.
| 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: | September 1975 |
| Identification Number: | CS-RR-008 |
| 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: | |
| URI: | http://wrap.warwick.ac.uk/id/eprint/46306 |
Actions (login required)
 |
View Item |
