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_22: A uniform generation procedure for NP is an algorithm that, given any input in a fixed NP-language, outputs a uniformly distributed NP-witness for membership of the input in the language. We present a uniform generation procedure for NP that runs in probabilistic polynomial time with an NP-oracle. This improves upon results of M. (1986, Theoret. Comput. Sci.43, 169?188), which either require a ?P2 oracle or obtain only almost uniform generation. Our procedure utilizes ideas originating in the works of M. Sipser, and L. Stockmeyer (respectively, 1983, in Proceedings of the 15th Annual Symposium on the Theory of Computing, ACM, New York), and (1986).
@cite_27: 
@cite_5: Abstract The class of problems involving the random generation of combinatorial structures from a uniform distribution is considered. Uniform generation problems are, in computational difficulty, intermediate between classical existence and counting problems. It is shown that exactly uniform generation of ‘efficiently verifiable’ combinatorial structures is reducible to approximate counting (and hence, is within the third level of the polynomial hierarchy). Natural combinatorial problems are presented which exhibit complexity gaps between their existence and generation, and between their generation and counting versions. It is further shown that for self-reducible problems, almost uniform generation and randomized approximate counting are inter-reducible, and hence, of similar complexity.
@cite_20: We study a time bounded variant of Kolmogorov complexity. This notion, together with universal hashing, can be used to show that problems solvable probabilistically in polynomial time are all within the second level of the polynomial time hierarchy. We also discuss applications to the theory of probabilistic constructions.
@cite_12: There are several computational problems that can be formulated as problems of counting the number of objects having a certain property. Valiant [22] has introduced the class #P which includes a variety of counting problems such as counting the number of perfect matchings in a graph, computing the permanent of a matrix [22], finding the size of a backtrack search tree [14], and computing the probability that a network remains connected when links can fail with a certain probability [23]. We define and study a class of restricted, but very natural, probabilistic sampling methods motivated by the particular counting problems mentioned above. Instead of “singleton sampling” the algorithm is allowed to sample a large set S ample; U in one step; the information returned from the sample is whether S contains any element having the property being counted. We attempt to classify the complexity of computing approximate solutions to problems in #P. The classification is done in terms of the polynomial-time hierarchy (for short, P-hierarchy) [21]. We give a relativization result that complements a recent result of Sipser and Gaacute;c [19] that BPP is contained in the second level of the P-hierarchy.
In many applications of constrained counting, such as in probabilistic reasoning, exact counting may not be critically important, and approximate counts suffice. Even when exact counts are important, the inherent complexity of the problem may force one to work with approximate counters. Jerrum, Valiant, and Vazirani @cite_5 showed that approximate counting of solutions of CNF formulas, to within a given tolerance factor, can be done with high confidence in randomized polynomial time using an oracle. A key result of @cite_5 states that for many problems, generating solutions is inter-reducible with approximate counting; hence, they have similar complexity. Building on the Sipser's and Stockmeyer's early work @cite_20 @cite_12 , Bellare, Goldreich, and Petrank @cite_22 later showed that in fact, an -oracle suffices for generating solutions of CNF formulas in randomized polynomial time. Unfortunately, these deep theoretical results have not been successfully reduced to practice. Our experience in implementing these techniques indicates that they do not scale in practice even to small problem instances involving few tens of variables @cite_27 .