Computación de la función de partición

Question

Hay en cualquier algoritmo conocido relativamente eficientes para calcular el función de partición < Span Class="Math-contenedor"> $ P (n) $ Para un Dado $ n $ ? ¿Qué se sabe sobre la clase de complejidad de este problema en función de $ n $ ?

Tal vez me esté perdiendo algo trivial aquí, pero aparte de enumerar algunas definiciones recurrentes de esta función y algunos de sus asintóticos, no veo esta información precisa (clase de complejidad y algoritmos conocidos con su tiempo de ejecución / complejidad espacial) En cualquiera de estos artículos:

• partición (teoría del número)
• función de partición (teoría del número)

Answer 1

Johansson le dio un algoritmo de tiempo casi lineal (¡en términos del tamaño de la producción!) En su papel implementación eficientede la fórmula Hardy-Ramanujan-Rademacher .Este trabajo se menciona al final de la Artículo de Wikipedia en la función de partición.