Hardness of Approximating Sigma 2 p Minimization Problems.
Christopher Umans · 1999
We show that a number of natural optimization problems in the second level of the Polynomial Hierarchy are \\Sigma p 2 -hard to approximate to within n ffl factors, for specific ffl ? 0. 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 n 1\\Gammaffl inapproximability results for some of these problems. We also prove inapproximability of a variant of an NP optimizationproblem, Monotone Minimum Satisfying Assignment, to within an n ffl factor using the same technique. 1. Introduction One of the earliest approximation algorithms for an NP optimization problem was Johnson's greedy algorithm for approximating SET COVER to within a factor of ln n, where n is the number of elements in the ground set [11]. Proving a matching ina...