We know that $\#P \subseteq P$ implies that $P = NP$. But is there any reason why a $1.001^n$ time algorithm shouldn't exist for a given $\#P$-hard problem?

  • 2
    $\begingroup$ In addition to the answer below I'll note that generally there's considered to be no fundamental difference between a $1.001^n$ time algorithm and a $583^n$ time algorithm, because a linear change to measuring the size of the input (which is generally considered a valid transformation of a problem) will change one into the other. Note that this sort of change doesn't alter whether a problem is in $\Theta(n)$, $\Theta(n^2)$, all of $P$, $NP$-complete, etc. $\endgroup$ Apr 2 at 21:28

1 Answer 1


An $1.001^n$ algorithm for a #P-hard problem can certainly exist, this would not imply anything that we do not know.

Note that there are much smaller functions for which this still holds. For example, quasipolynomial time: $O(2^{(\log n)^c})$ for some constant $c>1$.

In general, we do not know of a super-polynomial lower bound for a #P problem.

  • $\begingroup$ Thank you very much $\endgroup$
    – Simd
    Apr 2 at 18:20

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.