Email this article On a Relation Between the Depth and Complexity of Monotone Boolean Formulas
- Authors: Sergeev I.S.1
-
Affiliations:
- Scientific and Research Institute Kvant
- Issue: Vol 13, No 4 (2019)
- Pages: 746-752
- Section: Article
- URL: https://journals.rcsi.science/1990-4789/article/view/213294
- DOI: https://doi.org/10.1134/S1990478919040161
- ID: 213294
Cite item
Open Access
Access granted
Subscription Access
Abstract
We present a sequence of monotone Boolean functions whose depth over the basis {∧, ∨} is c > 1.06 times greater than the logarithm of the formula complexity.
Keywords
About the authors
I. S. Sergeev
Scientific and Research Institute Kvant
Author for correspondence.
Email: isserg@gmail.com
Russian Federation, Chetvyortyi Likhachyovskii per. 15, Moscow, 125438
Supplementary files
