The complexity of two-level logic minimization

The complexity of two-level logic minimization is a topic of interest to both CAD specialists and computer science theoreticians. In the logic synthesis community, two-level logic minimization forms the foundation for more complex optimization procedures that have significant real-world impact. At the same time, the computational complexity of two-level logic minimization has posed challenges since the beginning of the field in the 60's; indeed some central questions have been resolved only within the last few years, and others remain open. This recent activity has classified some logic optimization problems of high practical relevance, such as finding the minimal sum-of-products form, and maximal term expansion and reduction. This paper surveys progress in the field, with self-contained expositions of fundamental early classifications, an account of the recent advances, and new results due to the authors. We include an introduction to the relevant concepts and terminology from computational complexity, as well a discussion of the major remaining open problems in the complexity of logic minimization.