Random generation and counting
Ehrhard Behrends · Advanced lectures in mathematics · 2000
Sometimes it happens that one is dealing with a set S for which it is easy to check that it is finite but for which there seems to be no simple way to determine the number of elements within reasonable time. There are even situations where this problem is NP -hard so that exact counting is in a sense impossible. However, by using Markov chains one can treat the weaker problem of approximate counting , a connection which has been systematically studied by Sinclair and others (see [70] and the literature cited there). These keywords were added by machine and not by the authors. This process is experimental and the keywords may be updated as the learning algorithm improves.