| Abstract |
|
We show that a number of natural optimization problems in the second level of the Polynomial Hierarchy are \math hard to approximate to within \math factors, for specific \math. The main technical tool is the use of explicit dispersers to achieve strong, direct inapproximability results. The problems we consider include Succinct Set Cover, Minimum Equivalent DNF, and other problems relating to DNF minimization. Under a slightly stronger complexity assumption, our method gives optimal \math inapproximability results for some of these problems. We also prove inapproximability of a variant of an NP optimization problem, Monotone Minimum Satisfying Assignment, to within an \math factor using the same technique.
|
 Additional Information
|
Index Terms- polynomial hierarchy, logic minimization, hardness of approximation, dispersers, computational complexity
Citation:
Christopher Umans,
"Hardness of Approximating Minimization Problems,"
focs,
p. 465,
40th Annual Symposium on Foundations of Computer Science,
1999
|
