Computing della funzione di partizione

Question

ci sono in qualsiasi algoritmo conosciuto relativamente efficiente per calcolare il funzione di partizione < Class Class="Math-Container"> $ P (N) $ per una determinata class class="container di matematica"> $ N $ ? Ciò che è noto sulla classe Complexity Class di questo problema in funzione di $ N $ ?

Forse mi manca qualcosa di banale qui, ma oltre a elencare alcune definizioni ricorrenti di questa funzione e alcuni dei loro asintotici, non vedo queste informazioni precise (classe di complessità e algoritmi noti con la loro complessità di runtime / spazio) In uno dei due articoli:

.
• partizione (teoria del numero)
• funzione di partizione (teoria dei numeri)

Answer 1

Johansson ha dato un algoritmo di tempo quasi lineare (in termini di dimensioni dell'output!) Nel suo documento implementazione efficientedella formula hardy-ramanujan-rademacher .Questo lavoro è menzionato alla fine del Articolo di wikipedia sulla funzione di partizione.