How hard is counting the number of solutions?
Counting complexity requires counting the number of distinct solutions. These function problems are at least as difficult as deciding if the instance has a solution.
Counting complexity most commonly refers to #P (number-P or sharp-P). Each problem in #P requires computing the number of accepting paths of a nondeterministic Turing machine which runs in polynomial time. #P-complete problems include #SAT and counting the number of solutions of many NP-complete decision problems. However, counting the number of perfect matchings in a bipartite graph is also #P-complete: deciding whether a bipartite graph has a perfect matching can be established in polynomial time. The same applies to #2-SAT: the decision version is in P.
