3

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.


1

I assume $X,Y$ and $Z$ are languages. Now if a language $A$ is polynomial-time reducible to another language $B$ this means there exists a function $f$ that can be computed in $O(n^k)$ such that: $$p\in A \iff f(p) \in B$$ Now if such a function $f_{xy}$ exists for $X$ and $Y$ and such a function $f_{yz}$ for $Y$ and $Z$, you can construct a new function $...


1

It's true: Assume $Y\in NP$. Now let $N$ be the poly time verifier for $Y$. Lets also call the poly time reduction $\phi$. Then, notice that $x\in X\iff\phi(x)\in Y\iff \exists w.N(\phi(x),w)$. Therefore, let us build the poly time verifier for $X$ as follows: $M(x,w):$ Compute $\phi(x)$ in poly time Emulate $N(\phi(x),w)$ and accept if and only if $N$ ...


Only top voted, non community-wiki answers of a minimum length are eligible