2
$\begingroup$

Are there in any relatively efficient known algorithms to compute the partition function $P(n)$ for a given $n$? What's known about the complexity class of this problem as a function of $n$?

Perhaps I'm missing something trivial here, but other than listing some recurrent definitions of this function and some of their asymptotics, I don't see this precise information (complexity class, and known algorithms with their runtime/space complexity) in either of these articles:

Improve this question
$\endgroup$
3
  • 1
    $\begingroup$ The Wikipedia article summarizes all known information about this question. $\endgroup$
    – Yuval Filmus
    Apr 13, 2020 at 16:08
  • 2
    $\begingroup$ Check last paragraph of the second article: "Techniques for implementing the Hardy–Ramanujan–Rademacher formula efficiently on a computer are discussed by Johansson (2012), who shows that {\displaystyle p(n)}p(n) can be computed in time {\displaystyle O(n^{1/2+\varepsilon })}{\displaystyle O(n^{1/2+\varepsilon })} for any {\displaystyle \varepsilon >0}\varepsilon >0. This is near-optimal in that it matches the number of digits of the result.[19] ..." $\endgroup$
    – Yuval Filmus
    Apr 13, 2020 at 16:19
  • $\begingroup$ Ah +1 thanks @YuvalFilmus - I had originally checked the first link, and then read quickly through the second one but didn't get any search hits for the keywords 'algorithm', 'complexity', 'runtime' or 'class' in either of them. Reading the 2nd one all the way to the end would've helped :). So it's in $P$ (assuming e.g. input size = $n$) then? $\endgroup$
    – Amelio Vazquez-Reina
    Apr 13, 2020 at 16:23

1 Answer 1

Reset to default
4
$\begingroup$

Johansson gave a nearly linear time algorithm (in terms of the output size!) in his paper Efficient implementation of the Hardy-Ramanujan-Rademacher formula. This work is mentioned at the very end of the Wikipedia article on the partition function.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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