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 November 1998 | public
Book Section - Chapter

The Minimum Equivalent DNF Problem and Shortest Implicants

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).

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.

Additional details

Created:
August 19, 2023
Modified:
January 13, 2024