Counting problem (complexity)

<h2 id="counting-complexity-class">Counting complexity class</h2>
<p class="note">See also: <a href="/facts/%25E2%2599%25AFP/tY95TU7t">#P</a> and <a href="/facts/%25E2%2599%25AFP-complete/M6QgPJY6">#P-complete</a></p>
<p>Just as NP has <a href="/facts/NP-complete/NFPv56DU">NP-complete</a> problems via <a href="/facts/Many-one_reduction/YUKNlYPh">many-one reductions</a>, #P has #P-complete problems via <a href="/facts/Parsimonious_reduction/q41sFqcY">parsimonious reductions</a>, problem transformations that preserve the number of solutions.<a class="footnote-ref" id="fnref:1" href="#fn:1"><sup>1</sup></a>
</p>
<h2 id="see-also">See also</h2>
<ul><li><a href="/facts/GapP/7ekKtbQF">GapP</a></li></ul>

<h2 id="external-links">External links</h2>
<ul><li><a href="https://planetmath.org/CountingProblem">"counting problem"</a>. <i><a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a></i>.</li>
<li><a href="https://planetmath.org/CountingComplexityClass">"counting complexity class"</a>. <i><a href="/facts/PlanetMath/wphPCtLf">PlanetMath</a></i>.</li></ul>

<h2 id="references">References</h2>

<ol>
<li id="fn:1"><p>Barak, Boaz (Spring 2006). "Complexity of counting" (PDF). Princeton University. <a href="https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf" target="_blank">https://www.cs.princeton.edu/courses/archive/spring06/cos522/count.pdf</a> <a href="#fnref:1" class="footnote-back-ref">↩</a></p></li>
</ol>

Counting problem (complexity) open-in-new

Counting problem (complexity)