This article is cited in 4 papers

Part 2. Special Issues in Intellectual Systems Theory

The complexity of multidimensional rectangular circuits design

T. Sitdikov


Abstract: A model of rectangular multidimensional circuits is considered in this paper. Logic gates are placed in cells of $d$-dimensional mesh. Each pair of adjacent cells is connected by a bus with at most $k$ wires. We establish Shannon function upper bound $\frac{2^n}{\min(n,d \log k)}$ for the complexity of this type of circuits.

Keywords: multidimensional circuits, multilayer circuits, Shannon function asymptotics, circuit complexity.