Geodesic
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

Voir la notice de l'article provenant de la source Math-Net.Ru

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$). 
@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},
     publisher = {mathdoc},
     volume = {4},
     number = {6},
     year = {1968},
     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
PB  - mathdoc
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
%I mathdoc
%U http://geodesic.mathdoc.fr/item/MZM_1968_4_6_a4/
%G ru
%F MZM_1968_4_6_a4
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/