Minimum area layout of series-parallel transistor networks is NP-hard

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