## The VLSI complexity of Boolean functions.(English)Zbl 0551.94025

Logic and machines: decision problems and complexity, Proc. Symp., Münster/Ger. 1983, Lect. Notes Comput. Sci. 171, 397-407 (1984).
[For the entire collection see Zbl 0538.00005.]
The authors consider the area complexity of implementation of Boolean functions by VLSI circuits (Thompson’s model). Any such a circuit is a bounded convex region in the plane which is divided into unit cells as in the regular grid. Each cell may contain one basic switching element or at most 2 crossing wires. Every Boolean function can be implemented with the area complexity $$O(2^ n)$$, and there are functions with lower bound on the complexity of the same type.
Reviewer: A.Slisenko

### MSC:

 94C10 Switching theory, application of Boolean algebra; Boolean functions (MSC2010) 68Q25 Analysis of algorithms and problem complexity

Zbl 0538.00005