On the circuit implementation problem [combinatorial logic circuits]

The authors consider the problem of selecting an implementation of each circuit module from a cell library to satisfy overall delay and area, or delay and power requirements. Two versions of the circuit implementation problem, the basic circuit implementation problem and the general circuit implementation problem, are shown to be NP-hard. A pseudo-polynomial-time algorithm for the basic circuit implementation problem on series-parallel circuits is developed, and heuristics for the basic circuit implementation problem on general circuits are formulated. The run times for the heuristics are tabulated