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


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


Zbl 0538.00005