# Does the existence of an $\alpha$-approximation scheme for a problem $f$ imply there exists a fully polynomial (deterministic) approximation scheme?

If you have an $$\alpha$$-approximation algorithm $$A$$ for some problem $$f \in \#P$$, such that (for $$0 < \alpha \leq 1$$) $$\alpha f(x) \leq A(x) \leq \frac{f(x)}{\alpha},$$ does that automatically imply that you can reduce that accuracy range and have a fully polynomial approximation scheme, $$B$$, such that (for $$\varepsilon > 0$$) $$(1 - \varepsilon)f(x) \leq B(x) \leq (1 + \varepsilon)f(x)$$

I'm not really sure what would be the best way to prove or disprove this. One thought would be to show that this property is true for $$\#SAT$$ and then showing that all problems in $$\#P$$ reduce to #SAT and thus would have the same property? Although I'm also not sure how to go about proving this for $$\#SAT$$? Would appreciate any insight!

EDIT: made sure that $$\alpha$$ and $$\varepsilon$$ are both strictly greater than zero.

• What are your thoughts? Have you tried to disprove it?
– D.W.
Apr 20, 2022 at 21:19
• This certainly works for some problems, for example $\#SAT$. Apr 20, 2022 at 21:20
• Are you sure you want to allow $\alpha = 0$ and $\epsilon = 0$? Apr 20, 2022 at 21:21