Size-depth tradeoff in non-monotone Boolean formulae |
| |
| Authors: | Beate Commentz-Walter Juergen Sattler |
| |
| Affiliation: | 1. IBM Deutschland, Entwicklung und Forschung, Sch?naicher Str. 220, 7030, B?blingen, Germany (Fed. Rep.)
2. Fachbereich Mathematik, Johann-Wolfgang-Goethe-Universit?t, 6000, Frankfurt, Germany (Fed. Rep.)
|
| |
| Abstract: | Summary Formula size and depth are two important complexity measures of Boolean functions. We study the tradeoff between those two measures: We give an infinite set of Boolean functions and show for nearly each of them: There is no formula over “and”, “or”, “negation” computing it optimal with respect to both measures. That implies a logarithmic lower bound on circuit depth. |
| |
| Keywords: | |
| 本文献已被 SpringerLink 等数据库收录！ |
|
