Polynomial-time counting reduction

Relation to other kinds of reduction

As a special case, a parsimonious reduction is a polynomial-time transformation ${\displaystyle f}$ 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 ${\displaystyle g}$.

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. A functional problem ${\displaystyle Y}$ is said to be ♯P-hard if there exists a polynomial-time counting reduction from every problem ${\displaystyle X}$ in ♯P to ${\displaystyle Y}$. If, in addition, ${\displaystyle Y}$ itself belongs to ♯P, then ${\displaystyle Y}$ is said to be ♯P-complete. (Sometimes, as in Valiant's original paper proving the completeness of the permanent of 0–1 matrices, a weaker notion of reduction, Turing reduction, is instead used for defining ♯P-completeness.)

The usual method of proving a problem ${\displaystyle Y}$ in ♯P to be ♯P-complete is to start with a single known ♯P-complete problem ${\displaystyle X}$ and find a polynomial-time counting reduction from ${\displaystyle X}$ to ${\displaystyle Y}$. If this reduction exists, then there exists a reduction from any other problem in ♯P to ${\displaystyle Y}$, obtained by composing a reduction from the other problem to ${\displaystyle X}$ with the reduction from ${\displaystyle X}$ to ${\displaystyle Y}$.