Improved inapproximability factors for some Σ^p₂ minimization problems

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 Σ^p₂-hard to approximate to within factors of n^(1/3−ϵ) and ^(n1/2−ϵ) (where the previous results achieved n^(1/4−ϵ)), for arbitrarily small constant ϵ > 0. For one problem shown to be inapproximable to within n^(1/2−ϵ), 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.

Files

Additional details