I would like to ask about the computational complexity of the problem of generating integers so that the obtained distribution is asymptotic to the Gaussian distribution. Any related reference is very appreciated.

More precisely, consider the following problem $\mathcal{P}$: generate $n$ integers between $-N$ and $N$ so that after scaling the interval to $[-1,1]$, one gets a distribution statistically close to Gaussian distribution, as $n, N$ tend to infinity. Is $\mathcal{P}$ NP-hard?

  • $\begingroup$ you could start from a Poisson distribution (even without any computation, by using a physical gadget); there are many other computationally efficient methods, see en.wikipedia.org/wiki/… $\endgroup$ Dec 21, 2020 at 9:44
  • $\begingroup$ Thank you. I am actually interested in the complexity class of generating Gaussian distribution, not quite in concrete methods. Very sorry if my question is misleading $\endgroup$ Dec 21, 2020 at 9:49
  • 2
    $\begingroup$ pseudo-random-number generators work in polynomial time, for true randomness you could use a quantum bit; why would this be computationally hard? $\endgroup$ Dec 21, 2020 at 11:02


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.