Appendix A: Notation

Second, N and the function's computational complexity are bounded by a polynomial in M . If there is an algorithm which generates an approximate sample from an RBM's distribution Note that Mψ (M) is still polynomial in M . However, Theorem 1 states that there is no such polynomial time algorithm if RP null= NP . An example is visualized in Figure 1. Another possibility to obtain Gaussian noise would be the following. The soft-rounding function is differentiable everywhere.