A Caltech Library Service

Complexity of two-level logic minimization

Umans, Christopher and Villa, Tiziano and Sangiovanni-Vincentelli, Alberto L. (2006) Complexity of two-level logic minimization. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 25 (7). pp. 1230-1246. ISSN 0278-0070. doi:10.1109/TCAD.2005.855944.

See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Sangiovanni-Vincentelli, Alberto L.0000-0003-1298-8389
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.
Subject Keywords:Computational complexity, logic design, logic minimization, two-level logic
Issue or Number:7
Record Number:CaltechAUTHORS:UMAieeetcadics06
Persistent URL:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:4830
Deposited By: Archive Administrator
Deposited On:11 Sep 2006
Last Modified:08 Nov 2021 20:20

Repository Staff Only: item control page