Name
Abstract | ||
|---|---|---|
The complexity of two-level logic minimization is a topic of interest to both computer-aided design (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 1960s; 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 (SOP) form and maximal term expansion and reduction. This paper surveys progress in the field with self-contained expositions of fundamental early results, an account of the recent advances, and some new classifications. It includes 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 |
Year | DOI | Venue |
|---|---|---|
2006 | 10.1109/TCAD.2005.855944 | Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions |
Keywords | DocType | Volume |
computational complexity,logic CAD,minimisation,multivalued logic,computational complexity,computer-aided design,logic design,logic optimization problems,logic synthesis,maximal term expansion,minimal sum-of-products,two-level logic minimization,Computational complexity,logic design,logic minimization,two-level logic | Journal | 25 |
Issue | ISSN | Citations |
7 | 0278-0070 | 38 |
PageRank | References | Authors |
1.50 | 18 | 3 |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Christopher Umans | 1 | 879 | 55.36 |
| Villa, T. | 2 | 47 | 2.93 |
| Alberto L. Sangiovanni-Vincentelli | 3 | 11385 | 1881.40 |