Show Summary Details
## Quick Reference

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*=*NP*.

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.

See all related items in Oxford Index »

##### Reference entries

in
* A Dictionary of Computing
*
Reference Entry

Users without a subscription are not able to see the full content. Please,
subscribe
or login to access all content.