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

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

Use this Persistent URL to link to this item:


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
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.
Funding AgencyGrant Number
NSF Graduate Research FellowshipUNSPECIFIED
Other Numbering System:
Other Numbering System NameOther Numbering System ID
INSPEC Accession Number6128822
Record Number:CaltechAUTHORS:20120119-070934161
Persistent URL:
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:
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:28844
Deposited By: Ruth Sustaita
Deposited On:19 Jan 2012 15:56
Last Modified:19 Jan 2012 15:56

Repository Staff Only: item control page