Constrained sampling and counting are two fundamental problems in artificial intelligence with a diverse range of applications, spanning probabilistic reasoning and planning to constrained-random verification. While the theory of these problems was thoroughly investigated in the 1980s, prior work either did not scale to industrial size instances or gave up correctness guarantees to achieve scalability. Recently, we proposed a novel approach that combines universal hashing and SAT solving and scales to formulas with hundreds of thousands of variables without giving up correctness guarantees. This paper provides an overview of the key ingredients of the approach and discusses challenges that need to be overcome to handle larger real-world instances.
@cite_35: In the area of statistical physics, Monte Carlo algorithms based on Markov chain simulation have been in use for many years. The validity of these algorithms depends crucially on the rate of convergence to equilibrium of the Markov chain being simulated. Unfortunately, the classical theory of stochastic processes hardly touches on the sort of non-asymptotic analysis required in this application. As a consequence, it had previously not been possible to make useful, mathematically rigorous statements about the quality of the estimates obtained. Within the last ten years, analytical tools have been devised with the aim of correcting this deficiency. As well as permitting the analysis of Monte Carlo algorithms for classical problems in statistical physics, the introduction of these tools has spurred the development of new approximation algorithms for a wider class of problems in combinatorial enumeration and optimization. The “Markov chain Monte Carlo” method has been applied to a variety of such problems, and often provides the only known efficient (i.e., polynomial time) solution technique.
@cite_4: The class of @math -complete problems is a class of computationally eqivalent counting problems (defined by the author in a previous paper) that are at least as difficult as the @math -complete problems. Here we show, for a large number of natural counting problems for which there was no previous indication of intractability, that they belong to this class. The technique used is that of polynomial time reduction with oracles via translations that are of algebraic or arithmetic nature.
@cite_50: This beginning graduate textbook describes both recent achievements and classical results of computational complexity theory. Requiring essentially no background apart from mathematical maturity, the book can be used as a reference for self-study for anyone interested in complexity, including physicists, mathematicians, and other scientists, as well as a textbook for a variety of courses and seminars. More than 300 exercises are included with a selected hint set.
@cite_2: Two complexity classes, PP and (+)P, are compared with PH (the polynomial-time hierarchy). The main results are as follows: (1) every set in PH is reducible in a certain sense to a set in PP, an (2) every set in PH is reducible to a set in (+)P under randomized polynomial-time reducibility with two-sided bounded error probability. It follows from these results that neither PP nor (+)P is a subset of or equivalent to PH unless PH collapses to a finite level. This is strong evidence that both classes are strictly harder than PH. >
Constrained counting, the problem of counting the number of solutions of a propositional formula, is known as . It is @math -complete @cite_4 , where is the set of counting problems associated with decision problems. Theoretical investigations of have led to the discovery of deep connections in complexity theory @cite_2 @cite_4 , and there is strong evidence for its hardness @cite_50 . It is also known that an efficient algorithm for constrained would yield a fully polynomial randomized approximation scheme (FPRAS) for -complete inference problems @cite_35 -- a possibility that lacks any evidence so far and is widely disbelieved.