Counting problem (complexity)

In computational complexity theory and computability theory, a counting problem is a type of computational problem that is obtained by strengthening a decision problem. For example, the SAT problem asks: "Given a Boolean formula, is there a truth-value assignment such that it evaluates to True?". The corresponding counting problem, called #SAT, asks: "Given a Boolean formula, how many truth-value assignments are there such that it evaluates to True?". And in general, the counting problem corresponding to a decision problem X is called #X, where # is the number sign. Counting complexity techniques have significant applications in clarifying the relation between complexity classes of P, NP, PH, etc, in circuit complexity, and in interactive proof systems.

In computational complexity theory and computability theory, a counting problem is a type of computational problem that is obtained by strengthening a decision problem. For example, the SAT problem asks: "Given a Boolean formula, is there a truth-value assignment such that it evaluates to True?". The corresponding counting problem, called #SAT, asks: "Given a Boolean formula, how many truth-value assignments are there such that it evaluates to True?". And in general, the counting problem corresponding to a decision problem X is called #X, where # is the number sign. Counting complexity techniques have significant applications in clarifying the relation between complexity classes of P, NP, PH, etc, in circuit complexity, and in interactive proof systems. Let c_R(x)=\vert\{y\mid R(x,y)\}\vert \, be the counting function. That is, it counts the total number of admissible solutions. This is a function problem, not a decision problem. In order to conform to the standard format in computational complexity theory, we use the standard trick of converting a function problem to a decision problem, using the graph of the function. Let \#R=\{(x,y)\mid y\leq c_R(x)\} . That is, it is the set of all points on or below the curve of c_R(x) . While it appears that computing c_R(x) is harder than deciding whether some point (x, y) belongs to \# R , in fact c_R can be Cook-reduced to \# R using binary search on the value of c_R(x) , provided that c_R(x) is bounded by O(2^{\mathsf{poly}(|x|)}) . Concretely, one tests with (x, 0), (x, 1), \dots, (x, 2^n), \dots, (x, 2^{n^2}), \dots until one finds an element not in \#R , then backtracks to pinpoint the exact value of c_R(x) . In particular, c_R(x) must be bounded by O(2^{\mathsf{poly}(|x|)}) if it is FP, that is, computable in polynomial time by a Turing machine, since otherwise the machine will not have enough time to produce the full output. Throughout this article, we assume that c_R(x) is FP. This then allows us to switch between the decision-formulation with \# R and the function-formulation c_R fluidly without further comment. ==Classes== For any problem instance x_A of A , f maps to a problem instance f(x_A) of B , such that the number of solutions to x_A is computed by mapping the number of solutions to f(x_A) using g : c_A(x_A) = g(c_B(f(x_A))) Counting analogs of many natural NP-complete problems are #P-complete, but the opposite is not the case: Some decision problems correspond to #P-complete counting problems, even if they are in P, or even trivially decidable. For example, the 01-permanent counting problem is ♯P-complete under polynomial-time many-one counting reduction. This problem is equivalent to counting perfect matchings in a bipartite graph. Deciding whether perfect matchings exist in a bipartite graph is polynomial-time by the Hopcroft–Karp algorithm. There are some other problems that take polynomial time to decide, but are #P-complete to count: Spanning trees of a graph. Eulerian cycles of a directed graph. Perfect matchings of a planar graph. There are some problems that are trivial to decide, but #P-complete to count: Satisfying assignments to a monotone Boolean formula (one without negation symbol). There always exists at least one, by setting all variables to True. Non-cliques in a graph of size \lceil n/2\rceil , where n is the number of vertices. If the whole graph has any pair of vertices not connected by an edge, then there exists such a non-clique. Spanning forests of a bipartite planar graph. There always exists at least one. Linear extensions to a partial ordering on a finite set. There always exists at least one. There are some counting problems known to be #P-hard, but possibly exceeding #P: Given two graphs, count the number of graph isomorphisms between them. This is known to be computable in polynomial time given an NP-oracle. Given a graph, count the number of subgraphs that are Hamiltonian. ⊕P is defined to be Mod 2 P. It asks: "Given a problem instance, is the number of solutions even or odd?". It is low in itself: \oplus \mathsf{P}^{\oplus \mathsf{P}} = \oplus \mathsf{P} . C = P asks: "Given a problem instance, is the gap zero?". It is proven to be the complement of nondeterministic quantum polynomial-time (coNQPT). # L, C = L, Mod k L, ⊕L, etc are the logspace analogs of #P, C = P, Mod k P, ⊕P, etc. The matrix determinant function is #L-complete. As for oracle machines using #P-oracles, we have \mathsf{PP}^{\mathsf{PH}}\subset \mathsf{P}^{\#\mathsf{P}} = \mathsf{P}^{\mathsf{PP}}\subset \mathsf{PSPACE} Also, \mathsf{PH}\subset \mathsf{P}^{\#\mathsf{P}[1]} , that is, any problem in the polynomial hierarchy class is solvable in polynomial time, if we allow a single call to a #P-oracle. This is called Toda's theorem, and it won Seinosuke Toda the Gödel prize in 1998. There is strong evidence that many naturally occurring counting classes (PP, C = P, Mod k P, etc) are strictly harder than PH, since it is proven that if they are not strictly harder than PH, then the PH collapses, which is widely considered to be unlikely. ==References== ==External links== https://complexityzoo.net/Complexity_Zoo

Text derived from https://en.wikipedia.org/w/index.php?oldid=1373726047 under CC BY-SA 4.0; modifications have been made.