  Fourier phase retrieval, which seeks to reconstruct a signal from its Fourier
magnitude, is of fundamental importance in fields of engineering and science.
In this paper, we give a theoretical understanding of algorithms for Fourier
phase retrieval. Particularly, we show if there exists an algorithm which could
reconstruct an arbitrary signal ${\mathbf x}\in {\mathbb C}^N$ in $
\mbox{Poly}(N) \log(1/\epsilon)$ time to reach $\epsilon$-precision from its
magnitude of discrete Fourier transform and its initial value $x(0)$, then
$\mathcal{ P}=\mathcal{NP}$. This demystifies the phenomenon that, although
almost all signals are determined uniquely by their Fourier magnitude with a
prior conditions, there is no algorithm with theoretical guarantees being
proposed over the past few decades. Our proofs employ the result in
computational complexity theory that Product Partition problem is NP-complete
in the strong sense.
