# Polynomial reduction, #P-hard problems, and approximations

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?

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