The Minimum Equivalent DNF Problem and Shortest Implicants

We prove that the Minimum Equivalent DNF problem is /spl Sigma//sub 2//sup 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 /spl Sigma//sub 2//sup p/-complete, and /spl Sigma//sub 2//sup p/-hard to approximate to within an n/sup 1/2-/spl epsiv// factor. When the input is a circuit, approximation is /spl Sigma//sub 2//sup p/-hard to within an n/sup 1-/spl epsiv// factor. However, when the input is a DNF formula, the shortest implicant problem cannot be /spl Sigma//sub 2//sup p/-complete unless /spl Sigma//sub 2//sup p/=NP[log/sup 2/n]/sup NP/.

Authors

• Chris Umans

Keywords

• Logic
• Minimization
• Polynomials
• Computer science
• Electronic switching systems
• Boolean functions
• Circuits
• Variant Of Problem
• Boolean Function
• Minimalist
• Proof Of Theorem
• L-arginine
• Estimation Algorithm
• Additional Term
• New Variables
• Positive Instances
• Final Term
• Negative Instances
• Proof Of Claim
• Term In Formula