Minimum area layout of series-parallel transistor networks is NP-hard
Sourish Chakravarty, Xin He, Srivaths Ravi · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1991
Functional cells are a physical realization of complex MOS gates. Efficient algorithms for minimizing the width of a functional cell are known. Every solution to the width minimization problem leads to a cell of a certain height. It is shown that, even for functional cells of complex MOS gates represented by series-parallel transistor networks, the problem of finding a solution of minimum width that also minimizes the height is NP-hard.>