RUS  ENG
Full version
JOURNALS // Intelligent systems. Theory and applications // Archive

Intelligent systems. Theory and applications, 2023 Volume 27, Issue 1, Pages 91–133 (Mi ista501)

Part 3. Mathematical models

Lower estimate of potential for a class of volume circuits

A. A. Efimov

Lomonosov Moscow State University, Faculty of Mechanics and Mathematics

Abstract: In this paper, volume circuits are considered, which are the embeddings of Boolean circuits in space. For volume circuits, the lower bound on the potential is obtained. Potential is a measure of circuit activity equal to the number of gates that produce one on a given input. It is shown that for almost all partial operators with $n$ inputs and $m$ outputs, the potential of the volume circuit that implements them is not less than $ \frac{m \sqrt[3]{d}}{\min^{2/3}(m, log_2 d)} $, where $d$ is the size of the domain.

Keywords: Boolean circuits, volume circuits, circuit complexity, circuit activity, potential.



© Steklov Math. Inst. of RAS, 2024