Abstract
Circuit size, branching program size, and formula size of Boolean functions, denoted by C(f), BP(f), and L(f), are the most important complexity measures for Boolean functions. Often also the formula size L*(f) over the restricted basis {∨, ∧, ⌝} is considered. It is well-known that C(f) ≤ 3 BP(f), BP(f) ≤ L*(f), L*(f) ≤ L(f) 2, and C(f) ≤ L(f) - 1. These estimates are optimal. But the inequality BP(f) ≤ L(f) 2 can be improved to BP(f) ≤ 1.360 L(f) β, where β = log4(3 + √5) < 1.195.
The first and second author have been supported by DFG grant We 1066/8-1.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
L. Babai, P. Pudlák, V. Rödl, and E. Szemerédi. Lower bounds to the complexity of symmetric Boolean functions. Theoretical Computer Science, 74:313–323, 1990.
D. A. Barrington. Bounded-width polynomial-size branching programs recognize exactly those languages in NC1. Journal of Computer and System Sciences, 38:150–164, 1989.
J. Cai and R. J. Lipton. Subquadratic simulations of circuits by branching programs. In Proc. of the 30th IEEE Symp. on Foundations of Computer Science (FOCS), 568–573, 1989.
R. Cleve. Towards optimal simulations of formulas by bounded-width programs. Computational Complexity, 1:91–105, 1991.
R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison-Wesley, 1994.
V. M. Krapchenko. Complexity of the realization of a linear function in the class of π-circuits. Math. Notes Acad. Sci. USSR, 10:21–23, 1971.
É. I. Neciporuk. A Boolean function. Soviet Mathematics Doklady, 7(4):999–1000, 1966.
I. Wegener. The Complexity of Boolean Functions. Wiley-Teubner, 1987.
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 1999 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Sauerhoff, M., Wegener, I., Werchner, R. (1999). Relating Branching Program Size and Formula Size over the Full Binary Basis. In: Meinel, C., Tison, S. (eds) STACS 99. STACS 1999. Lecture Notes in Computer Science, vol 1563. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-49116-3_5
Download citation
DOI: https://doi.org/10.1007/3-540-49116-3_5
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-65691-3
Online ISBN: 978-3-540-49116-3
eBook Packages: Springer Book Archive