Restricted Boltzmann Machines are Hard to Approximately Evaluate or Simulate
Philip M. Long, Rocco A. Servedio · 2010
Restricted Boltzmann Machines (RBMs) are a type of probability model over the Boolean cube {−1, 1} n that have recently received much attention. We establish the intractability of two basic computational tasks involving RBMs, even if only a coarse approximation to the correct output is required. We first show that assuming P ̸ = NP, for any fixed positive constant K (which may be arbitrarily large) there is no polynomial-time algorithm for the following problem: given an n-bit input string x and the parameters of a RBM M, output an estimate of the probability assigned to x by M that is accurate to