Parsimonious reduction

Let ${\displaystyle x}$ be an instance of problem ${\displaystyle X}$. A Parsimonious reduction ${\displaystyle R}$ from problem ${\displaystyle X}$ to problem ${\displaystyle Y}$ is a reduction such that the number of solutions to ${\displaystyle x}$ is equal to the number of solutions to problem ${\displaystyle R(x)}$.[1] If such a reduction exists, and if we have an oracle that counts the number of solutions to ${\displaystyle R(x)}$ which is an instance of ${\displaystyle Y}$, then we can design an algorithm that counts the number of solutions to ${\displaystyle x}$, the corresponding instance of ${\displaystyle X}$. Consequently, if counting the number of solutions to the instances of ${\displaystyle X}$ is hard, then counting the number of solutions to ${\displaystyle Y}$ must be hard as well.

Just as many-one reductions are important for proving NP-completeness, parsimonious reductions are important for proving completeness for counting complexity classes such as #P.[1] Because parsimonious reductions preserve the property of having a unique solution, they are also used in game complexity, to show the hardness of puzzles such as sudoku where the uniqueness of the solution is an important part of the definition of the puzzle.[2]

Specific types of parsimonious reductions may be defined by the computational complexity or other properties of the transformation algorithm. For instance, a polynomial-time parsimonious reduction is one in which the transformation algorithm takes polynomial time. These are the types of reduction used to prove #P-Completeness.[1] In parameterized complexity, FPT parsimonious reductions are used; these are parsimonious reductions whose transformation is a fixed-parameter tractable algorithm and that map bounded parameter values to bounded parameter values by a computable function.[3]

Polynomial-time parsimonious reductions are a special case of a more general class of reductions for counting problems, the polynomial-time counting reductions.[4]

One common technique used in proving that a reduction ${\displaystyle R}$ is parsimonious is to show that there is a bijection between the set of solutions to ${\displaystyle x}$ and the set of solutions to ${\displaystyle R(x)}$ which guarantees that the number of solutions to both problems is the same.

The class #P contains the counting versions of NP decision problems. Given an instance ${\displaystyle x}$ of an NP decision problem ${\displaystyle X,}$ the problem ${\displaystyle \#x}$ asks for the number of solutions to problem ${\displaystyle x.}$ The examples of #P-completeness below rely on the fact that #SAT is #P-complete.