CaltechAUTHORS
  A Caltech Library Service

The Minimum Equivalent DNF Problem and Shortest Implicants

Umans, Christopher (1998) The Minimum Equivalent DNF Problem and Shortest Implicants. In: 39th Annual Symposium on Foundations of Computer Science. Annual IEEE Symposium on Foundations of Computer Science. IEEE Computer Society , Los Alamitos, CA, pp. 556-563. ISBN 0-8186-9172-7 http://resolver.caltech.edu/CaltechAUTHORS:20120119-070934161

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item: http://resolver.caltech.edu/CaltechAUTHORS:20120119-070934161

Abstract

We prove that the Minimum Equivalent DNF problem is _Σ2 ^(p-)complete, resolving a conjecture due to L.J. Stockmeyer (1976). The proof involves as an intermediate step a variant of a related problem in logic minimization, namely, that of finding the shortest implicant of a Boolean function. We also obtain certain results concerning the complexity of the shortest implicant problem that may be of independent interest. When the input is a formula, the shortest implicant problem is Σ_2^(p-)complete, and Σ_2^(p-)hard to approximate to within an n^(1/2-ε) factor. When the input is a circuit, approximation is Σ_2^(p-)hard to within an n^(1-ε) factor. However, when the input is a DNF formula, the shortest implicant problem cannot be Σ_2^(p-)complete unless Σ_2^p=NP[log^2_n]^(NP).


Item Type:Book Section
Related URLs:
URLURL TypeDescription
http://dx.doi.org/10.1109/SFCS.1998.743506DOIUNSPECIFIED
http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=743506&tag=1PublisherUNSPECIFIED
Additional Information:© 1998 IEEE. Issue Date: Nov 1998. Date of Current Version: 06 August 2002. Supported by NSF grant CCR-9626361 and an NSF Graduate Research Fellowship. We would like to thank Christos Papadimitriou for suggesting this problem, and many useful discussions.
Funders:
Funding AgencyGrant Number
NSFCCR-9626361
NSF Graduate Research FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number6128822
Record Number:CaltechAUTHORS:20120119-070934161
Persistent URL:http://resolver.caltech.edu/CaltechAUTHORS:20120119-070934161
Official Citation:Umans, C.; , "The minimum equivalent DNF problem and shortest implicants," Foundations of Computer Science, 1998. Proceedings.39th Annual Symposium on , vol., no., pp.556-563, 8-11 Nov 1998 doi: 10.1109/SFCS.1998.743506 URL: http://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=743506&isnumber=15971
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28844
Collection:CaltechAUTHORS
Deposited By: Ruth Sustaita
Deposited On:19 Jan 2012 15:56
Last Modified:19 Jan 2012 15:56

Repository Staff Only: item control page