A model of computation for VLSI with related complexity results
Bernard Chazelle, Louis M. Monier · 1981
We propose a new model of computation for VLSI which is a refinement of previous models and makes the additional assumption that the time for propagating information is linear in the distance. Our approach is motivated by the failure of previous models to allow for realistic asymptotic analysis. While accommodating for basic laws of physics, this model tries to be most general and technology-independent. Thus, from a complexity viewpoint, it is especially suited for deriving lower bounds and trade-offs. We present new results for a number of problems including fan-in, addition, transitive functions, matrix multiplication, and sorting.