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



© Steklov Math. Inst. of RAS, 2025