Computando a função de partição

Question

Existem em algum algoritmo conhecido relativamente eficiente para calcular o função de partição < Span Class="contêiner matemática"> $ P (n) $ para uma determinada $ n $ ? O que se sabe sobre a classe complexidade desse problema como uma função da $ n $ ?

Talvez eu esteja perdendo algo trivial aqui, mas além de listar algumas definições recorrentes desta função e algumas de suas assínquióticas, não vejo essas informações precisas (classe complexidade e algoritmos conhecidos com sua complexidade de tempo de execução / espaço) Em qualquer um desses artigos:

• partição (teoria do número)
• função de partição (teoria do número)

Answer 1

Johansson deu um algoritmo de tempo quase linear (em termos do tamanho da saída!) Em seu papel Eficiente implementaçãoda fórmula Hardy-Ramanujan-Rademacher .Este trabalho é mencionado no final do Artigo de Wikipedia Na função de partição.