Editing ♯P-complete (section)

==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]].