Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

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.

history | excerpt history