Editing ♯P-complete (section)

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