Abstract:
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$).
Fulltext:
PDF file (687 kB)
