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 October 1999 | public
Book Section - Chapter

Hardness of Approximating Σ^(p)_(2) Minimization Problems

Abstract

We show that a number of natural optimization problems in the second level of the Polynomial Hierarchy are Σ^(p)_(2)-hard to approximate to within n factors, for specific ε > 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-ε) 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 n^ε factor using the same technique.

Additional Information

© 1999 IEEE. Issue Date: 1999; Date of Current Version: 06 August 2002. Supported in part by NSF grant CCR-9626361 and an NSF Graduate Research Fellowship. We wish to thank Christos Papadimitriou for many useful discussions.

Additional details

Created:
August 19, 2023
Modified:
October 24, 2023