Consider two statements.

Statement 1: The problem #3SAT (finding the number of satisfying instances to a 3SAT problem) is #P-hard.

Statement 2: Additively approximating #3SAT upto $\pm 2^{n/2}$ error is #P-hard (a proof is given here).

Now, consider any other problem B that is also #P-hard. The solutions to B lie in the set $[0, c]$, for $c > 0$ (for example, for #3SAT, $c = 2^{n}$, as there can be, at maximum, $2^{n}$ satisfying assignments).

Are Statements 1 and 2 sufficient to show that any $\pm \frac{c 2^{n/2}}{2^{n}}$ additive error approximation to B is also #P-hard?

More generally, given that an additive error approximation to a particular hard problem of a complexity class is also hard for that class, does this hold (upto a normalizing constant) for any hard problem of that same class? If not, is this statement true for multiplicative approximations? And are there explicit counterexamples?

  • 1
    $\begingroup$ It is insufficient. Nothing magical happens unless you can prove that it happens. $\endgroup$ – Yuval Filmus Mar 22 at 7:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.