Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published July 1, 2006 | public
Journal Article Open

Complexity of two-level logic minimization

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.

Additional Information

© Copyright 2006 IEEE. Reprinted with permission. Manuscript received October 4, 2004; revised March 10, 2005. [Posted online: 2006-06-05] The work of C. Umans was supported by National Science Foundation (NSF) under Grant CCF-0346991. The work of T. Villa was supported by Project for Advanced Research of Architecture and Design of Electronic Systems (PARADES). The work of A. L. Sangiovanni-Vincentelli was supported by the Center for Hybrid and Embedded Software Systems (CHESS) under Contract NSF ITR Grant CCR-0225610. This paper was recommended by Associate Editor L. Stok. The authors thank D. S. Johnson for kindly providing a hardcopy of Masek's technical report. T. Villa thanks R. Brayton, K. Keutzer, and A. Oliveira for related discussions.

Files

UMAittttcadics06.pdf
Files (343.7 kB)
Name Size Download all
md5:7420a52f9bbb4b86af54aaba99a908a5
343.7 kB Preview Download

Additional details

Created:
August 22, 2023
Modified:
October 16, 2023