The Minimum Equivalent DNF Problem and Shortest Implicants

摘要

We prove that the Minimum Equivalent DNF problem is ΣP2-complete, resolving a conjecture due to Stockmeyer. We also consider the complexity and approximability of a related optimization problem in the second level of the polynomial hierarchy, that of finding shortest implicants of a Boolean function. We show that when the input is given as a DNF, this problem is complete for a complexity class above coNP utilizing O(log2 n)-limited nondeterminism. When the input is given as a formula or circuit, the problem is ΣP2-complete, and ΣP2-hard to approximate within factors of n1/2−ϵ and n1−ϵ, respectively.