DocumentCode :
3450571
Title :
Hardness of approximating Σ2p minimization problems
Author :
Umans, Christopher
Author_Institution :
Comput. Sci. Div., California Univ., Berkeley, CA, USA
fYear :
1999
fDate :
1999
Firstpage :
465
Lastpage :
474
Abstract :
We show that a number of natural optimization problems in the second level of the Polynomial Hierarchy are Σ2p -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 n1-ε 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
Keywords :
computational complexity; minimisation; set theory; Σ2p minimization problem approximation; DNF minimization; Minimum Equivalent DNF; Monotone Minimum Satisfying Assignment; NP optimization problem; Polynomial Hierarchy; Succinct Set Cover; direct inapproximability results; explicit dispersers; hardness; natural optimization problems; optimal inapproximability results; stronger complexity assumption; Approximation algorithms; Bipartite graph; Circuit synthesis; Computer science; Greedy algorithms; Logic circuits; Machinery; Minimization methods; Polynomials;
fLanguage :
English
Publisher :
ieee
Conference_Titel :
Foundations of Computer Science, 1999. 40th Annual Symposium on
Conference_Location :
New York City, NY
ISSN :
0272-5428
Print_ISBN :
0-7695-0409-4
Type :
conf
DOI :
10.1109/SFFCS.1999.814619
Filename :
814619
Link To Document :
بازگشت