Reduced Error Pruning of branching programs cannot be approximated to within a logarithmic factor

摘要

In this paper, we prove under a plausible complexity hypothesis that Reduced Error Pruning of branching programs is hard to approximate within log~(1-δ) n, for every δ > 0, where n is the number of description variables, a measure of the problem's complexity. The result holds under the assumption that NP problems do not admit deterministic, slightly superpolynomial time algorithms: NP ￠ TIME(|I|~(O(loglog|I|))). This improves on a previous result that only had a small constant inapproximability ratio, and puts a fairly strong constraint on the efficiency of potential approximation algorithms. The result also holds for read-once and μ-branching programs.