Abstract:
In the paper the complexity of realization of Boolean functions
by formulas over various bases is investigated.
In terms of the complexity of almost all Boolean functions, bases
are, in a sense, equal in rights.
At the same time, individual sequences of functions admit essentially
simpler realization over some bases than over other ones. In this connection, of interest is such a method of comparison of bases
which takes into account the complexity of realization of some individual
sequences of functions.
Such a method was proposed by O. B. Lupanov and then developed
by B. A. Subbotovskaya and V. A. Stetsenko. The research was supported by the Russian Foundation for Basic Research,
grant 99–01–01175, and also by
Federal Program ‘State support for integration of higher education
and fundamental science for 1997–2000’, grant 2.1–473.