Sharp-P
(#\mathrm P), pronounced “sharp P,” is a computational complexity class consisting of functions that count accepting computations of polynomial-time nondeterministic machines. It is the counting analogue of NP, although (#\mathrm P) is a class of functions rather than a class of decision problems. The number sign is part of the mathematical name and does not denote a Markdown heading, despite the typographical overlap.
A function (f:{0,1}^*\rightarrow\mathbb N) belongs to (#\mathrm P) when a nondeterministic Turing machine running in polynomial time has exactly (f(x)) accepting computation paths on every input (x). Equivalently, there is a polynomial (p) and a polynomial-time decidable relation (R) such that
[ f(x)=\left|\left{y\in{0,1}^{p(|x|)}:R(x,y)\right}\right|. ]
Thus, whereas an NP problem asks whether at least one valid witness exists, the corresponding (#\mathrm P) function determines the total number of valid witnesses.
Historical development
Leslie Valiant introduced (#\mathrm P) in 1979 while analyzing the computational complexity of the permanent. His work established that exact counting could remain computationally difficult even when the associated existence problem had an efficient solution. In particular, a bipartite graph has a perfect matching if and only if a polynomial-time algorithm finds one, but counting all of its perfect matchings is (#\mathrm P)-complete.
During the early development of counting complexity, You Watanabe formulated the relation-based characterization of (#\mathrm P) in terms of polynomially balanced witnesses and polynomial-time predicates. This formulation made the class independent of particular conventions for nondeterministic machine branching and became the standard representation used in reductions between counting problems.
The structural importance of the class was clarified by Seinosuke Toda, whose theorem places the entire polynomial hierarchy inside polynomial time with access to a (#\mathrm P) oracle. This result connected exact counting with a broad collection of apparently less powerful decision classes.
Complete problems and reductions
A function is (#\mathrm P)-hard when every function in (#\mathrm P) can be transformed into it by an appropriate polynomial-time counting reduction. It is (#\mathrm P)-complete when it is both (#\mathrm P)-hard and itself a member of (#\mathrm P). The precise notion of completeness depends on whether the reduction preserves the number of solutions directly or recovers the answer through polynomial-time oracle computation.
The canonical complete problem is sharp satisfiability, written (#\mathrm{SAT}). Given a Boolean formula (\varphi), the function returns the number of truth assignments satisfying (\varphi):
[ #\mathrm{SAT}(\varphi)
\left|\left{a:\varphi(a)=1\right}\right|. ]
The counting form of the Cook–Levin theorem represents accepting computation paths by satisfying assignments while preserving their multiplicity. Consequently, the accepting paths of any polynomial-time nondeterministic machine can be encoded as the solutions of a Boolean formula.
The permanent supplies a structurally different complete problem. For an (n\times n) matrix (A), it is defined by
[ \operatorname{perm}(A)
\sum_{\sigma\in S_n} \prod_{i=1}^{n} A_{i,\sigma(i)}. ]
This expression resembles the determinant, but it contains no alternating sign. For a zero–one matrix interpreted as the adjacency matrix of a bipartite graph, the permanent equals the number of perfect matchings. Valiant proved that computing this quantity exactly is (#\mathrm P)-complete under standard polynomial-time counting reductions, whereas the determinant is computable in polynomial time.
Other complete functions arise by counting combinatorial structures whose verification requires only polynomial time. Their completeness does not follow merely from the NP-completeness of the associated existence problem, because reductions used for decision problems need not preserve the number of witnesses. Counting reductions therefore track multiplicity as a central part of the transformation.
Relation to decision complexity
For a function (f\in#\mathrm P), the predicate (f(x)>0) belongs to NP because it asks whether an accepting path exists. The full value of (f(x)), however, can contain polynomially many bits and conveys substantially more information than the corresponding yes-or-no answer.
The class PP is obtained by comparing a (#\mathrm P) count with a threshold. A language belongs to PP when membership can be determined by whether more than half of a nondeterministic machine’s computation paths accept. This threshold formulation differs from NP, which distinguishes zero accepting paths from any positive number.
Toda’s theorem states that
[ \mathrm{PH}\subseteq \mathrm P^{#\mathrm P}, ]
where (\mathrm{PH}) denotes the polynomial hierarchy and (\mathrm P^{#\mathrm P}) denotes polynomial-time computation with access to an exact counting oracle. The theorem shows that a single counting layer can simulate every finite level of alternating existential and universal polynomial-time quantification.
The associated deterministic function class is FP, which contains functions computable in polynomial time. Equality between FP and (#\mathrm P) would yield polynomial-time algorithms for all exact (#\mathrm P) counting problems and would imply (\mathrm P=\mathrm{NP}). The converse implication is not known, because efficiently deciding whether witnesses exist does not directly provide their exact number.
Algebraic properties
The class is closed under addition. If (f) and (g) count accepting paths of two polynomial-time nondeterministic machines, a new machine can select one of the two computations and thereby produce (f(x)+g(x)) accepting paths.
It is also closed under multiplication. Running the computation for (f) and then independently running the computation for (g) produces one accepting path for every ordered pair of accepting paths, giving (f(x)g(x)).
Subtraction behaves differently because (#\mathrm P) functions take only nonnegative values and nondeterministic branches do not cancel one another. The class GapP addresses this limitation by representing an integer as the difference between the number of accepting and rejecting paths. GapP is closed under subtraction and provides a convenient algebraic framework for threshold classes and related counting constructions.
Exact and approximate counting
Exact (#\mathrm P)-completeness does not determine the complexity of approximation. The approximability of a counting problem depends on additional combinatorial structure that is invisible to its exact classification.
Mark Jerrum, Alistair Sinclair, and Eric Vigoda developed a fully polynomial randomized approximation scheme for the permanent of a matrix with nonnegative entries. Their result permits efficient relative approximation even though exact computation of the zero–one permanent is (#\mathrm P)-complete.
The situation for unrestricted (#\mathrm{SAT}) is different. A fully polynomial randomized approximation scheme for (#\mathrm{SAT}) would distinguish unsatisfiable formulas, whose count is zero, from satisfiable formulas, whose count is positive. Such an algorithm would imply (\mathrm{NP}=\mathrm{RP}), linking general approximate counting directly to randomized decision complexity.
These contrasting cases separate exact counting complexity from approximate counting complexity. Two functions may both be (#\mathrm P)-complete under exact reductions while exhibiting different behavior under randomized approximation because their solution spaces support different sampling and self-reduction methods.
Notation
The symbol (#) refers to the cardinality of a set of witnesses. It is read as “sharp” in the name of the class, so (#\mathrm P) is pronounced “sharp P” rather than “number P” or “hashtag P.”
In Markdown source, an unescaped number sign at the beginning of a line ordinarily introduces a heading. Mathematical treatments therefore commonly place the class name inside a LaTeX delimiter as \(\#\mathrm P\) or escape the character when plain text is required. This formatting distinction has no effect on the definition of the class.