0
$\begingroup$

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?

$\endgroup$
3
  • $\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$ Commented 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$ Commented 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$ Commented Dec 21, 2020 at 11:02

0

You must log in to answer this question.

Browse other questions tagged .