Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR09-107 | 28th October 2009 11:01

Improved inapproximability factors for some \Sigma_2^p minimization problems

RSS-Feed




TR09-107
Authors: Kevin Dick, Chris Umans
Publication: 28th October 2009 11:12
Downloads: 3372
Keywords: 


Abstract:

We give improved inapproximability results for some minimization problems in the second level of the Polynomial-Time Hierarchy. Extending previous work by Umans [Uma99], we show that several variants of DNF minimization are \Sigma_2^p-hard to approximate to within factors of n^{1/3-\epsilon} and n^{1/2-\epsilon} (where the previous results achieved n^{1/4 - \epsilon}), for arbitrarily small constant \epsilon > 0. For one problem shown to be inapproximable to within n^{1/2 - \epsilon}, we give a matching O(n^{1/2})-approximation algorithm, running in randomized polynomial time with access to an NP oracle, which shows that this result is tight assuming the PH doesn't collapse.



ISSN 1433-8092 | Imprint