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=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.
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.
More From encyclopedia.com
You Might Also Like
NEARBY TERMS
counting problem