Matematičeskie zametki, Tome 4 (1968) no. 6, pp. 649-658
Citer cet article
A. A. Sapozhenko. On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions. Matematičeskie zametki, Tome 4 (1968) no. 6, pp. 649-658. http://geodesic.mathdoc.fr/item/MZM_1968_4_6_a4/
@article{MZM_1968_4_6_a4,
author = {A. A. Sapozhenko},
title = {On the greatest length of a~dead-end disjunctive normal form for almost all {Boolean} functions},
journal = {Matemati\v{c}eskie zametki},
pages = {649--658},
year = {1968},
volume = {4},
number = {6},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/MZM_1968_4_6_a4/}
}
TY - JOUR
AU - A. A. Sapozhenko
TI - On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions
JO - Matematičeskie zametki
PY - 1968
SP - 649
EP - 658
VL - 4
IS - 6
UR - http://geodesic.mathdoc.fr/item/MZM_1968_4_6_a4/
LA - ru
ID - MZM_1968_4_6_a4
ER -
%0 Journal Article
%A A. A. Sapozhenko
%T On the greatest length of a dead-end disjunctive normal form for almost all Boolean functions
%J Matematičeskie zametki
%D 1968
%P 649-658
%V 4
%N 6
%U http://geodesic.mathdoc.fr/item/MZM_1968_4_6_a4/
%G ru
%F MZM_1968_4_6_a4
The maximal number $l(f)$ of conjunctions in a dead-end disjunctive normal form (d.n.f.) of a Boolean function $f $and the number $\tau(f)$ of dead-end d.n.f. are important parameters characterizing the complexity of algorithms for finding minimal d.n.f. It is shown that for almost all Boolean functions $l(f)\sim2^{n-1}$, $\log_2\tau(f)\sim2^{n-1}\log_2n\log_2\log_2n$ ($n\to\infty$).
