#P

#P
Name	#P
Type	Complexity class
Introduced	1979
Introduced by	Leslie Valiant
Related	NP, PP, #P-complete, P, PSPACE, BPP, FP

#P #P is a class of counting problems that captures the number of accepting paths of nondeterministic polynomial-time computations. It formalizes quantitative versions of decision problems by asking for the exact count of solutions rather than a yes/no answer, and serves as a central class in structural complexity theory, connecting to decision classes such as NP and probabilistic classes such as PP.

Definition and Formalism

Formally, #P is the set of functions f for which there exists a nondeterministic polynomial-time Turing machine M such that for every input x, f(x) equals the number of accepting computation paths of M on x. Alternative formalizations quantify over polynomial-time verifiable relations: f(x) = |{y : |y| ≤ p(|x|) and R(x,y) holds}| for some polynomial p and polynomial-time predicate R. This definition ties #P to machine models like the Turing machine and to complexity-theoretic constructs such as counting quantifiers and polynomial-time recognizability.

Complexity and Relationships to Other Classes

#P relates tightly to several major classes. Functions in #P generalize characteristic functions of languages in NP: a language L is in NP if and only if there exists a #P function g with L = {x : g(x) > 0}. The class FP consists of #P functions computable in deterministic polynomial time; FP ⊆ #P. Decision classes derive from #P via thresholding: PP comprises languages decidable by comparing a #P function to half the set of paths. Toda's theorem connects #P to the polynomial hierarchy by asserting that the polynomial hierarchy is contained in P^#P, showing that #P-oracles provide enormous power. Relative relationships include inclusions and oracle separations studied involving P, PSPACE, and randomized classes like BPP.

Complete Problems and Reductions

Completeness for #P is defined under polynomial-time counting reductions (parsimonious reductions, Turing reductions, or many-one reductions adapted to counting). The prototypical #P-complete problem under parsimonious reductions is counting satisfying assignments for Boolean formulas, known as #SAT. Other canonical #P-complete problems include counting perfect matchings in a bipartite graph (#PerfectMatching), enumerating Hamiltonian cycles, counting graph colorings for fixed k (e.g., #3-Colorings), and counting solutions to systems of linear equations over finite fields when parameterized appropriately. Reductions among these problems often preserve exact solution counts and exploit combinatorial constructions; many hardness proofs employ gadgets and polynomial interpolation to transform instance structures while maintaining count equivalence.

Algorithms and Approaches for #P Problems

Exact algorithms for #P problems are typically exponential-time; classical approaches include inclusion–exclusion, dynamic programming over tree decompositions (utilizing concepts from Courcelle's theorem indirectly through bounded treewidth), and transfer-matrix methods for combinatorial enumeration. Algebraic techniques leverage the permanent and determinant dichotomy: the determinant is computable in polynomial time (via Gaussian elimination) while the permanent is #P-complete (Valiant), motivating randomized approximations. Approximation algorithms and probabilistic techniques address intractability: fully polynomial randomized approximation schemes (FPRAS) exist for counting problems such as the number of perfect matchings in dense graphs under certain conditions (via Markov chain Monte Carlo methods like those originating from work connected to Jerrum, Sinclair, and Vigoda). Holographic algorithms and reductions by Valiant use linear-algebraic cancellations to yield polynomial-time solutions for special structured instances. Parameterized complexity studies count versions under parameters (e.g., counting k-matchings) and deliver fixed-parameter tractable (FPT) algorithms in restricted regimes.

Applications and Practical Implications

Counting complexity arises across computer science, combinatorics, statistical physics, and computational biology. Computing partition functions in models like the Ising model or computing network reliability in reliability theory are natural #P problems; exact evaluation corresponds to computing probabilities or normalizing constants in graphical models used in Bayesian networks and Markov random fields. In cryptography, hardness of counting underlies assumptions for certain cryptographic primitives and one-way function constructions. In database theory, provenance and counting query answers connect to #P. Practical algorithms focus on approximation, sampling, or exploiting structural restrictions (planarity, bounded genus, bounded degree) to make otherwise #P-hard problems tractable in applied settings.

Historical Development and Key Results

The class emerged from Leslie Valiant's 1979 formulation introducing #P and proving the #P-completeness of the permanent, establishing a cornerstone in counting complexity. Subsequent milestones include Toda's theorem relating #P to the polynomial hierarchy, Valiant and Vazirani's isolation lemma influencing randomized reductions, and the development of approximation paradigms via Markov chain Monte Carlo by Jerrum and Sinclair. The dichotomy results for counting constraint satisfaction problems elucidated by Bulatov, Dyer, Goldberg, Jerrum, and others mapped tractable versus #P-hard landscapes for classes of constraint languages. Work on holographic algorithms, the algebraic complexity of the permanent versus determinant, and refinements in parameterized counting complexity continue to shape the field. Major contributors include Leslie Valiant, Valiant's theorem contributors, Richard J. Lipton, Mihalis Yannakakis, Mark Jerrum, Alistair Sinclair, Valerie Kabanets, Venkatesan Guruswami, and many researchers in counting dichotomies and approximation.

Category:Computational complexity theory