RUS  ENG
Full version
JOURNALS // Vestnik Moskovskogo Universiteta. Seriya 1. Matematika. Mekhanika // Archive
Vestnik Moskov. Univ. Ser. 1. Mat. Mekh., 2020 Number 3, Pages 42–46 (Mi vmumm4327)
Short notes

Multilevel representation and complexity of circuits of unbounded fan-in gates

I. S. Sergeev

Research Institute "Kvant", Moscow

Abstract: A new simpler proof of the asymptotic $C(n)\sim\sqrt2\cdot2^{n/2}$ of the Shannon function of the circuit complexity over the basis of multi-input generalized conjunctions is obtained.

Key words: Boolean functions, Boolean circuits, complexity, multilevel representation.

UDC: 519.714

Received: 28.02.2018


 English version: Moscow University Mathematics Bulletin, Moscow University Måchanics Bulletin, 2020, 75:3, 121–125

Bibliographic databases:

© Steklov Math. Inst. of RAS, 2025