Kramer, M. R.; van Leeuwen, J. 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 Cited in 2 Documents 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 PDF BibTeX XML OpenURL