1
$\begingroup$

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.

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

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.