Approximating Succinct MaxSat
Christian Schallhart, Luca Trevisan · Journal of Logic and Computation · 2005
We study the approximability of the version of MAXSAT where exponentially large instances are succinctly represented using circuits. First, we prove that the NP-hardness for approximating MAXSAT can be lifted to a corresponding NEXP-hardness for approximating circuit-succinct MAXSAT for some constant performance ratio. Second, we consider the approximability of circuit-succinct MAXSAT with respect to lower complexity classes: in particular, we prove that computing (2 − ϵ)-approximate solutions for circuit-succinct MAXSAT is at least as hard as inverting one-way permutations. On the other hand, a simple randomized approximation algorithm computes a (2 + ϵ)-approximate solution with high probability. Recall that the standard (not succinctly represented) version of the MAXSAT problem is approximable to within a 0.78 factor and that the MAX3SAT problem is approximable to within a 7/8 factor.