Computing the partition function 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)
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.