Exact value of the nonmonotone complexity of Boolean functionsстатья
Информация о цитировании статьи получена из
Web of Science,
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 21 мая 2019 г.
Аннотация:We study the complexity of the realization of Boolean functions by circuits in infinite
complete bases containing all monotone functions with zero weight (cost of use) and finitely many
nonmonotone functions with unit weight. The complexity of the realization of Boolean functions in
the case where the only nonmonotone element of the basis is negation was completely described by
A. A. Markov: the minimum number of negations sufficient for the realization of an arbitrary Boolean
function f (the inversion complexity of the function f) is equal to ]log_2(d(f) + 1)[, where d(f)
is the maximum (over all increasing chains of sets of values of the variables) number of changes
of the function value from 1 to 0. In the present paper, this result is generalized to the case of
the computation of Boolean functions over an arbitrary basis B of prescribed form. It is shown
that the minimum number of nonmonotone functions sufficient for computing an arbitrary Boolean
function f is equal to ]log_2(d(f)/D(B) +1)[, where D(B) = max d(ω); the maximum is taken over
all nonmonotone functions ω of the basis B.