View source for ♯P

{{short description|Complexity class}}
{{Use mdy dates|date=January 2025}}{{correct title|#P|reason=#}}

In [[computational complexity theory]], the complexity class '''#P''' (pronounced "sharp P" or, sometimes "number P" or "hash P") is the set of the [[counting problem (complexity)|counting problem]]s associated with the [[decision problem]]s in the set '''[[NP (complexity)|NP]]'''. More formally, '''#P''' is the class of function problems of the form "compute ''f''(''x'')", where ''f'' is the number of accepting paths of a [[nondeterministic Turing machine]] running in [[Time complexity#Polynomial time|polynomial time]]. Unlike most well-known complexity classes, it is not a class of [[decision problem]]s but a class of [[function problem]]s. The most difficult, representative problems of this class are [[♯P-complete|#P-complete]].

==Relation to decision problems==
An '''NP''' decision problem is often of the form "Are there any solutions that satisfy certain constraints?" For example:
* Are there any subsets of a list of integers that add up to zero? ([[subset sum problem]])
* Are there any [[Hamiltonian cycle]]s in a given [[graph theory|graph]] with cost less than 100? ([[traveling salesman problem]])
* Are there any variable assignments that satisfy a given [[conjunctive normal form|CNF (conjunctive normal form)]] formula? ([[Boolean satisfiability problem]] or SAT)
* Does a univariate real polynomial have any positive roots? ([[Root finding]])

The corresponding '''#P''' function problems ask "how many" rather than "are there any".  For example:
* How many subsets of a list of integers add up to zero?
* How many Hamiltonian cycles in a given graph have cost less than 100?
* How many variable assignments satisfy a given CNF formula?
* How many roots of a univariate real polynomial are positive?

==Related complexity classes==
Clearly, a '''#P''' problem must be at least as hard as the corresponding '''NP''' problem.  If it's easy to count answers, then it must be easy to tell whether there are any answers—just count them and see whether the count is greater than zero. Some of these problems, such as [[root finding]], are easy enough to be in [[FP (complexity)|FP]], while others are [[♯P-complete|#P-complete]].

One consequence of [[Toda's theorem]] is that a [[Time complexity#Polynomial time|polynomial-time]] machine with a '''#P''' [[oracle machine|oracle]] ('''P'''<sup>'''#P'''</sup>) can solve all problems in '''[[PH (complexity)|PH]]''', the entire [[polynomial hierarchy]]. In fact, the polynomial-time machine only needs to make one '''#P''' query to solve any problem in '''PH'''. This is an indication of the extreme difficulty of solving '''#P'''-complete problems exactly.

Surprisingly, some '''#P''' problems that are believed to be difficult correspond to easy (for example linear-time) '''[[P (complexity)|P]]''' problems.  For more information on this, see [[sharp-P-complete|#P-complete]].

The closest decision problem class to '''#P''' is '''[[PP (complexity)|PP]]''', which asks whether a majority (more than half) of the computation paths accept. This finds the most significant bit in the '''#P''' problem answer. The decision problem class '''[[Parity P|⊕P]]''' (pronounced "Parity-P") instead asks for the least significant bit of the '''#P''' answer.

==Formal definitions==
'''#P''' is formally defined as follows:
: '''#P''' is the set of all functions <math>f:\{0,1\}^* \to \mathbb{N}</math> such that there is a polynomial time [[nondeterministic Turing machine]] <math>M</math> such that for all <math>x \in \{0,1\}^*</math>, <math>f(x)</math> equals the number of accepting branches in <math>M</math>'s computation graph on <math>x</math>.<ref name="Barak-Counting">{{cite web |last1=Barak |first1=Boaz |title=Complexity of counting |url=https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf |website=Computer Science 522: Computational Complexity |publisher=Princeton University |date=Spring 2006}}</ref> 

'''#P''' can also be equivalently defined in terms of a verifer. A decision problem is in '''[[NP (complexity)|NP]]''' if there exists a polynomial-time checkable [[certificate (complexity)|certificate]] to a given problem instance—that is, '''NP''' asks whether there exists a proof of membership for the input that can be checked for correctness in polynomial time. The class '''#P''' asks ''how many'' certificates there exist for a problem instance that can be checked for correctness in polynomial time.<ref name="Barak-Counting"/> In this context, '''#P''' is defined as follows:
: '''#P''' is the set of functions <math>f: \{0,1\}^* \to \mathbb{N}</math> such that there exists a polynomial <math>p: \mathbb{N} \to \mathbb{N}</math> and a polynomial-time [[deterministic Turing machine]] <math>V</math>, called the verifier, such that for every <math>x \in \{0,1\}^*</math>, <math>f(x)=\Big| \big \{y \in \{0,1\}^{p(|x|)} : V(x,y)=1 \big \} \Big| </math>.<ref>{{cite book |last1=Arora |first1=Sanjeev |last2=Barak|author1-link=Sanjeev Arora |first2=Boaz|author2-link=Boaz Barak |title=Computational Complexity: A Modern Approach |date=2009 |publisher=Cambridge University Press |isbn=978-0-521-42426-4|page=344}}</ref> (In other words, <math>f(x)</math> equals the size of the set containing all of the polynomial-size certificates).

==History==
The complexity class '''#P''' was first defined by [[Leslie Valiant]] in a 1979 article on the computation of the [[Permanent (mathematics)|permanent]] of a [[square matrix]], in which he proved that [[permanent is sharp-P-complete|permanent is #P-complete]].<ref>{{cite journal
  | author = Leslie G. Valiant
  | title = The Complexity of Computing the Permanent
  | journal = Theoretical Computer Science
  | volume = 8
  | pages = 189–201
  | publisher = [[Elsevier]]
  | date = 1979
  | doi = 10.1016/0304-3975(79)90044-6
  | issue = 2| doi-access = free
  }}</ref>

[[Larry Stockmeyer]] has proved that for every #P problem <math>P</math> there exists a [[randomized algorithm]] using an oracle for SAT, which given an instance <math>a</math> of <math>P</math> and <math>\epsilon > 0</math> returns with high probability a number <math>x</math> such that <math>(1-\epsilon) P(a) \leq x \leq (1+\epsilon) P(a)</math>.<ref>{{cite journal|doi=10.1137/0214060|journal=SIAM Journal on Computing|volume=14|issue=4|pages=849–861|date=November 1985|title=On Approximation Algorithms for #P|url=http://www.geocities.com/stockmeyer@sbcglobal.net/approx_sp.pdf|archive-url=https://web.archive.org/web/20091028104655/http://www.geocities.com/stockmeyer@sbcglobal.net/approx_sp.pdf|archive-date=2009-10-28|last1=Stockmeyer|first1=Larry}}</ref>  The runtime of the algorithm is polynomial in <math>a</math> and <math>1/ \epsilon</math>. The algorithm is based on the [[leftover hash lemma]].

==See also==
{{Portal|Computer programming}}
* {{Annotated link |Quantum_computing#Relation_to_computability_and_complexity_theory}}

== References ==
{{reflist}}

== External links ==

* {{CZoo|Class #P|Symbols#sharpp}}

{{ComplexityClasses}}

[[Category:Complexity classes]]