|
|
Intelligent systems. Theory and applications, 2023, Volume 27, Issue 1, Pages 91–133
(Mi ista501)
|
|
|
|
This article is cited in 1 scientific paper (total in 1 paper)
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.
Citation:
A. A. Efimov, “Lower estimate of potential for a class of volume circuits”, Intelligent systems. Theory and applications, 27:1 (2023), 91–133
Linking options:
https://www.mathnet.ru/eng/ista501 https://www.mathnet.ru/eng/ista/v27/i1/p91
|
|