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

Kramer, M. R.; van Leeuwen, J.

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

Keywords:

area complexity; Boolean functions; VLSI circuits; bounded convex region

Citations:

Zbl 0538.00005