View source for Polynomial-time counting reduction

{{Short description|Problem transformation for counting solutions}}
In the [[computational complexity theory]] of [[counting problem (complexity)|counting problem]]s, a '''polynomial-time counting reduction''' is a type of [[Reduction (complexity)|reduction]] (a transformation from one problem to another) used to define the notion of [[Complete (complexity)|completeness]] for the complexity class [[♯P]].{{r|gss}} These reductions may also be called '''polynomial many-one counting reductions''' or '''weakly parsimonious reductions'''; they are analogous to [[many-one reduction]]s for [[decision problem]]s and they generalize the [[parsimonious reduction]]s.{{r|cks}}

==Definition==
A polynomial-time counting reduction is usually used to transform instances of a known-hard problem <math>X</math> into instances of another problem <math>Y</math> that is to be proven hard. It consists of two functions <math>f</math> and <math>g</math>, both of which must be computable in [[polynomial time]]. The function <math>f</math> transforms inputs for <math>X</math> into inputs for <math>Y</math>, and the function <math>g</math> transforms outputs for <math>Y</math> into outputs for <math>X</math>.{{r|gss|cks}}

These two functions must preserve the correctness of the output. That is, suppose that one transforms an input <math>x</math> for problem <math>X</math> to an input <math>y=f(x)</math> for problem <math>Y</math>, and then one solves <math>y</math> to produce an output <math>z</math>. It must be the case that the transformed output <math>g(z)</math> is the correct output for the original input <math>x</math>. That is, if the input-output relations of <math>X</math> and <math>Y</math> are expressed as functions, then their [[function composition]] must obey the [[identity (mathematics)|identity]] <math>X=g\circ Y\circ f</math>. Alternatively, expressed in terms of [[algorithm]]s, one possible algorithm for solving <math>X</math> would be to apply <math>f</math> to transform the problem into an instance of <math>Y</math>, solve that instance, and then apply <math>g</math> to transform the output of <math>Y</math> into the correct answer for <math>X</math>.{{r|gss|cks}}

==Relation to other kinds of reduction==
As a special case, a [[parsimonious reduction]] is a polynomial-time transformation <math>f</math> on the inputs to problems that preserves the exact values of the outputs. Such a reduction can be viewed as a polynomial-time counting reduction, by using the [[identity function]] as the function <math>g</math>.{{r|gss|cks}}

==Applications in complexity theory==
A functional problem (specified by its inputs and desired outputs) belongs to the complexity class [[♯P]] if there exists a [[non-deterministic Turing machine]] that runs in polynomial time, for which the output to the problem is the number of accepting paths of the Turing machine. Intuitively, such problems count the number of solutions to problems in the complexity class [[NP (complexity)|NP]]. A functional problem <math>Y</math> is said to be ♯P-hard if there exists a polynomial-time counting reduction from every problem <math>X</math> in ♯P to <math>Y</math>. If, in addition, <math>Y</math> itself belongs to ♯P, then <math>Y</math> is said to be [[♯P-complete]].{{r|gss|cks}} (Sometimes, as in Valiant's original paper [[Sharp-P-completeness of 01-permanent|proving the completeness of the permanent of 0–1 matrices]], a weaker notion of reduction, [[Turing reduction]], is instead used for defining ♯P-completeness.{{r|val}})

The usual method of proving a problem <math>Y</math> in ♯P to be ♯P-complete is to start with a single known ♯P-complete problem <math>X</math> and find a polynomial-time counting reduction from <math>X</math> to <math>Y</math>. If this reduction exists, then there exists a reduction from any other problem in ♯P to <math>Y</math>, obtained by [[Function composition|composing]] a reduction from the other problem to <math>X</math> with the reduction from <math>X</math> to <math>Y</math>.{{r|gss|cks}}

==References==
{{reflist|refs=

<ref name=cks>{{citation
 | last1 = Creignou | first1 = Nadia
 | last2 = Khanna | first2 = Sanjeev | author2-link = Sanjeev Khanna
 | last3 = Sudan | first3 = Madhu | author3-link = Madhu Sudan
 | contribution = 2.2.2 Parsimonious reductions and ♯P-completeness
 | contribution-url = https://books.google.com/books?id=ZzW5AgAAQBAJ&pg=PA12
 | doi = 10.1137/1.9780898718546
 | isbn = 0-89871-479-6
 | mr = 1827376
 | pages = 12–13
 | publisher = Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA
 | series = SIAM Monographs on Discrete Mathematics and Applications
 | title = Complexity classifications of Boolean constraint satisfaction problems
 | year = 2001}}</ref>

<ref name=gss>{{citation
 | last1 = Gomes | first1 = Carla P. | author1-link = Carla Gomes
 | last2 = Sabharwal | first2 = Ashish
 | last3 = Selman | first3 = Bart | author3-link = Bart Selman
 | editor1-last = Biere | editor1-first = Armin
 | editor2-last = Heule | editor2-first = Marijn | editor2-link = Marijn Heule
 | editor3-last = van Maaren | editor3-first = Hans
 | editor4-last = Walsh | editor4-first = Toby
 | contribution = Chapter 20. Model Counting
 | isbn = 9781586039295
 | pages = 633–654
 | publisher = IOS Press
 | series = Frontiers in Artificial Intelligence and Applications
 | title = Handbook of Satisfiability
 | url = http://www.cs.cornell.edu/~sabhar/chapters/ModelCounting-SAT-Handbook-prelim.pdf
 | volume = 185
 | year = 2009}}. See in particular [https://books.google.com/books?id=YVSM3sxhBhcC&pg=PA634 pp. 634–635].</ref>

<ref name=val>{{citation
 | last = Valiant | first = L. G. | authorlink = Leslie Valiant
 | doi = 10.1016/0304-3975(79)90044-6
 | issue = 2
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 526203
 | pages = 189–201
 | title = The complexity of computing the permanent
 | volume = 8
 | year = 1979| doi-access = free
 }}</ref>

}}

[[Category:Reduction (complexity)]]