RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive

Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2013 Number 3, Pages 55–57 (Mi vmumm409)

This article is cited in 1 paper

Short notes

Orders of growth of Shannon functions for circuit complexity over infinite bases

O. M. Kasim-zade

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: It is shown that any function of one real variable being composition of rational functions with real coefficients, logarithms, and exponents and having an order of growth between $n$ and $2^{O(n^{1/2})}$ is an order of growth of the Shannon function for the circuit complexity over a certain infinite basis.

Key words: Boolean function, circuit of functional elements, complexity, Shannon function.

UDC: 519.7

Received: 20.06.2012


 English version:
Moscow University Mathematics Bulletin, Moscow University Mеchanics Bulletin, 2013, 68:3, 170–172

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025