# counting problem

**counting problem** **1.** The task of finding the number of elements of some set with a particular property. Such counting problems are usually encountered in combinatorics.

**2.** The task of counting the number of solutions to a problem. For example, to find the number of spanning trees of a given graph, there is a formula in terms of the determinant of a certain matrix that is computable in polynomial time. However there are other problems, like counting the number of Hamiltonian cycles in a given graph, that are expected to be difficult, because determining whether or not a graph has a Hamiltonian cycle is NP-complete (see P=NP question). Although it is possible to determine whether or not a graph has a perfect *matching* (a set of edges that do not meet each other but meet every vertex) in polynomial time, computing the number of such matchings can be done in polynomial time only if ** P**=

**P.**

*N*The matching problem referred to is, in the bipartite case, the same as computing the permanent of a 0–1 matrix, for which no good methods are known.

#### More From encyclopedia.com

#### You Might Also Like

#### NEARBY TERMS

**counting problem**