ABSTRACT
In computational complexity theory, we distinguish decision, optimization, counting and sampling problems. Although this book is about the computational complexity of counting and sampling, counting and sampling problems are related to decision and optimization problems. Counting problems are always at least as hard as their decision counterparts. Indeed, if we can tell, say, the number of perfect matchings in a graph G, then naturally we can tell if there exists a perfect matching in G: G contains a perfect matching if and only if the number of perfect matchings in G is at least 1.
