Computing the partition function

Question

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:

• Partition (number theory)
• Partition function (number theory)

• Yuval Filmus: The Wikipedia article summarizes all known information about this question.
• Yuval Filmus: 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] ..."
• Amelio Vazquez-Reina: 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?

Answer 1

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.