Editing ♯P-complete

{{short description|Complexity class}}
{{correct title|#P-complete|reason=#}}

The '''#P-complete''' problems (pronounced "sharp P complete" or "number P complete") form a [[complexity class]] in [[computational complexity theory]]. The problems in this complexity class are defined by having the following two properties:
*The problem is in [[♯P|#P]], the class of problems that can be defined as counting the number of accepting paths of a [[polynomial-time]] [[non-deterministic Turing machine]].
{{anchor|hashP-hard}}
*The problem is [[♯P|#P]]-hard, meaning that every other problem in #P has a [[Turing reduction]] or [[polynomial-time counting reduction]] to it. A counting reduction is a pair of polynomial-time transformations from inputs of the other problem to inputs of the given problem and from outputs of the given problem to outputs of the other problem, allowing the other problem to be solved using any subroutine for the given problem. A Turing reduction is an algorithm for the other problem that makes a polynomial number of calls to a subroutine for the given problem and, outside of those calls, uses polynomial time. In some cases [[parsimonious reduction]]s, a more specific type of reduction that preserves the exact number of solutions, are used.

<nowiki>#P-complete</nowiki> problems are at least as hard as [[NP-complete]] problems.<ref>{{cite journal |last1=Valiant |first1=Leslie G. |title=The Complexity of Enumeration and Reliability Problems |journal=SIAM Journal on Computing |date=August 1979 |volume=8 |issue=3 |pages=410–421 |doi=10.1137/0208032 |url=https://www.math.cmu.edu/~af1p/Teaching/MCC17/Papers/enumerate.pdf}}</ref> A polynomial-time algorithm for solving a #P-complete problem, if it existed, would solve the [[P versus NP problem]] by implying that P and NP are equal. No such algorithm is known, nor is a proof known that such an algorithm does not exist.

==Examples==
Examples of #P-complete problems include:
* How many different variable assignments will satisfy a given general Boolean formula? ([[Sharp-SAT|#SAT]])
* How many different variable assignments will satisfy a given [[disjunctive normal form|DNF]] formula?
* How many different variable assignments will satisfy a given [[2-satisfiability]] problem?
* How many [[perfect matching]]s are there for a given [[bipartite graph]]?
* What is the value of the [[Permanent (mathematics)|permanent]] of a given matrix whose entries are 0 or 1?  (See [[♯P-completeness of 01-permanent|#P-completeness of 01-permanent]].)
* How many [[graph coloring]]s using ''k'' colors are there for a particular graph ''G''?
* How many different [[linear extension]]s are there for a given [[partially ordered set]], or, equivalently, how many different [[topological sorting|topological orderings]] are there for a given [[directed acyclic graph]]?<ref>{{Cite journal
 | last1 = Brightwell | first1 = Graham R.
 | last2 = Winkler | first2 = Peter | author2-link = Peter Winkler
 | doi = 10.1007/BF00383444
 | issue = 3
 | journal = [[Order (journal)|Order]]
 | pages = 225–242
 | title = Counting linear extensions
 | volume = 8
 | year = 1991
 | s2cid = 119697949
 }}.</ref>

These are all necessarily members of the class [[♯P|#P]] as well. As a non-example, consider the case of counting solutions to a [[1-satisfiability]] problem: a series of variables that are each individually constrained, but have no relationships with each other. The solutions can be efficiently counted, by multiplying the number of options for each variable in isolation. Thus, this problem is in [[♯P|#P]], but cannot be #P-complete unless [[♯P|#P]]=[[FP (complexity)|FP]]. This would be surprising, as it would imply that [[P (complexity)|P]]=[[NP (complexity)|NP]]=[[PH (complexity)|PH]].

== Easy problems with hard counting versions ==

Some #P-complete problems correspond to easy ([[P (complexity)|polynomial time]]) problems. Determining the satisfiability of a Boolean formula in [[disjunctive normal form]] is easy: such a formula is satisfiable if and only if it contains a satisfiable conjunction (one that does not contain a variable and its negation),  whereas counting the number of satisfying assignments is #P-complete. Furthermore, deciding 2-satisfiability is easy compared to counting the number of satisfying assignments. [[Topological sorting|Topologically sorting]] is easy in contrast to counting the number of topological sortings. A single [[Matching (graph theory)|perfect matching]] can be found in polynomial time, but counting all perfect matchings is #P-complete.  The perfect matching counting problem was the first counting problem corresponding to an easy P problem shown to be #P-complete, in a 1979 paper by [[Leslie Valiant]] which also defined the class #P and the #P-complete problems for the first time.<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
  | year = 1979
  | doi = 10.1016/0304-3975(79)90044-6
  | issue = 2| doi-access = free
  }}</ref>

== Approximation ==

There are [[probabilistic algorithm]]s that return good approximations to some #P-complete problems with high probability. This is one of the demonstrations of the power of probabilistic algorithms.

Many #P-complete problems have a [[polynomial-time approximation scheme|fully polynomial-time randomized approximation scheme]], or "FPRAS," which, informally, will produce with high probability an approximation to an arbitrary degree of accuracy, in time that is polynomial with respect to both the size of the problem and the degree of accuracy required.  [[Mark Jerrum|Jerrum]], [[Leslie Valiant|Valiant]], and [[Vijay Vazirani|Vazirani]] showed that every #P-complete problem either has an FPRAS, or is essentially impossible to approximate; if there is any polynomial-time algorithm which consistently produces an approximation of a #P-complete problem which is within a polynomial ratio in the size of the input of the exact answer, then that algorithm can be used to construct an FPRAS.<ref>{{cite journal
  | author = Mark R. Jerrum |author2=Leslie G. Valiant |author3=Vijay V. Vazirani
  | title = Random Generation of Combinatorial Structures from a Uniform Distribution
  | journal = Theoretical Computer Science
  | volume = 43
  | pages = 169–188
  | publisher = Elsevier
  | year = 1986 
  | doi = 10.1016/0304-3975(86)90174-x | doi-access = free
  }}</ref>

== References ==

<references/>

== Further reading ==
* {{cite book
  | last = Vazirani
  | first = Vijay V.
  | title = Approximation Algorithms
  | publisher = Springer
  | year = 2003
  | location = Berlin
  | isbn = 3-540-65367-8 }}

{{ComplexityClasses}}

{{DEFAULTSORT:Sharp-P-Complete}}
[[Category:Complexity classes]]