RUS
ENG
Full version
JOURNALS
// Diskretnyi Analiz i Issledovanie Operatsii
// Archive
Diskretn. Anal. Issled. Oper.,
2019
Volume 26,
Issue 4,
Pages
108–120
(Mi da939)
On a relation between the depth and complexity of monotone Boolean formulas
I. S. Sergeev
Scientific and Research Institute «Kvant», 15 Chetvyortyi Likhachyovskii Lane, 125438 Moscow, Russia
Abstract:
We present a sequence of monotone Boolean functions whose depth over the basis
$\{\vee,\wedge\}$
is
$c>1.06$
times greater than the logarithm of the formula complexity. Tab. 1, bibliogr. 24.
Keywords:
Boolean formula, depth, complexity, monotone function.
UDC:
519.7
Received:
26.12.2018
Revised:
01.06.2019
Accepted:
05.06.2019
DOI:
10.33048/daio.2019.26.643
Fulltext:
PDF file (347 kB)
References
©
Steklov Math. Inst. of RAS
, 2025