This blog is devoted to the computational complexity of counting and sampling. #P is the complexity class which asks the number of witnesses of decision problems in NP. More precisely, it asks the number of witnesses that can be verified in polynomial time. How hard is to calculate this? One particular problem might be extremely hard, falling into the #P-complete class, the counting counterpart of NP-complete. Note that if anybody would be able to solve a #P-complete problem in polynomial time, it would automatically imply that P = NP, solving a one million dollar question. On the other hand, if somebody would prove that P = NP, it would not automatically imply that a #P-complete problem was solvable in polynomial time.

However, even the #P-complete problems are not equally hard. Some of the famous #P-complete problems like counting the number of linear extensions can be approximated well. This means that these problems are in FPRAS, ie. they can be approximated using a Fully Polynomial Randomized Approximation Scheme. And some of them cannot be approximated even in an FPRAS manner unless RP = NP. An example for this is counting the number of cycles in a directed graph, already appeared in the seminal paper of Jerrum, Valiant and Vazirani.

So counting problems might be easy, falling into FP (function polynomial), hard to calculate exactly but can be easily approximated or even cannot be approximated easily. Which counting problem fall into which class and why?

In many cases, approximate counting (FPAUS) and approximate sampling are equivalent. The standard tool for approximate sampling is the Markov chain (Monte Carlo), and another standard technique is (sequential) importance sampling. We will dedicate posts to these topics, too.

### Like this:

Like Loading...