New answers tagged counting-complexity
1
This is #P-hard, already for an arbitrary fixed constant approximation factor. As you noted, it allows you to approximate $|f(x)|$ for any GapP-function $f$, and therefore if $f$ is any #P (or GapP) function, it allows you to approximate $|f(x)-y|$ for a given $y$. With this, you can still compute $f(x)$ by a form of binary search.
Specifically, fix a ...
Top 50 recent answers are included
