This article is cited in 10 papers

The complexity of the realization of symmetrical functions by formulae

V. M. Khrapchenko

Institute of Applied Mathematics, Academy of Sciences of the USSR

Abstract: It is proved that every symmetric function in $k$-valued logic of $n$ arguments can be realized by a formula in any basis, the complexity of the formula not exceeding $n^C$, where $C$ is a constant depending on the basis. It is shown that in the case $k=2$, $C\leqslant 4,93$ for all bases.

UDC: 51.01

Received: 24.12.1970

 English version: Mathematical Notes, 1972, 11:1, 70–76

Bibliographic databases:

• 
•