Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR09-107 | 28th October 2009 11:01

#### Improved inapproximability factors for some $\Sigma_2^p$ minimization problems

TR09-107
Authors: Kevin Dick, Chris Umans
Publication: 28th October 2009 11:12
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.