Calculer la fonction de partition

Question

y a-t-il dans des algorithmes connus relativement efficaces pour calculer le Fonction de partition < SPAN CLASSE="MATH-CONTENEUR"> $ P (N) $ pour un $ N $ ? Ce qui est connu sur la classe la classe de complexité de ce problème en tant que fonction de $ n $ ?

Peut-être que je manque quelque chose de trivial ici, mais autre que d'énumérer certaines définitions récurrentes de cette fonction et une partie de leur asymptotique, je ne vois pas cette information précise (classe de complexité et algorithmes connus avec leur complexité d'exécution / espace) Dans l'un de ces articles:

• partition (théorie des nombres)
• Fonction de partition (théorie des nombres)

Answer 1

Johansson a donné un algorithme de temps presque linéaire (en termes de taille de sortie!) Dans son article Mise en œuvre efficacede la formule Hardy-Ramanujan-Rademacher .Ce travail est mentionné à la fin de la <-href="https://fr.wikipedia.org/wiki/partition_function_(Number_theory_function_(Number_theory)" rel="nofollow NOREFERRER"> Article Wikipedia sur la fonction de partition.