In computational complexity theory and game complexity, a parsimonious reduction is a transformation from one problem to another (a reduction) that preserves the number of solutions.
Informally, it is a bijection between the respective sets of solutions of two problems.
Parsimonious reductions are commonly used in computational complexity for proving the hardness of counting problems, for counting complexity classes such as #P. Additionally, they are used in game complexity, as a way to design hard puzzles that have a unique solution, as many types of puzzles require.
[1] If such a reduction exists, and if we have an oracle that counts the number of solutions to
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.
[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.
The class #P contains the counting versions of NP decision problems.
The hardness reduction from 3SAT to Planar 3SAT given by Lichtenstein[5] has the additional property that for every valid assignment of an instance of 3SAT, there is a unique valid assignment of the corresponding instance of Planar 3SAT, and vice versa.
The counting version of this problem asks for the number of Hamiltonian cycles in a given directed graph.
Seta Takahiro provided a reduction[6] from 3SAT to this problem when restricted to planar directed max degree-3 graphs.
Hence the reduction is parsimonious and Hamiltonian Cycle in planar directed max degree-3 graphs is #P-complete.
Consequently, the general version of Hamiltonian Cycle problem must be #P-complete as well.
Shakashaka is an example of how parsimonious reduction could be used in showing hardness of logic puzzles.
The decision version of this problem asks whether there is a solution to a given instance of the puzzle.
The counting version asks for the number of distinct solutions to such a problem.
The reduction from Planar 3SAT given by Demaine, Okamoto, Uehara and Uno[7] also provides a bijection between the set of solutions to an instance of Planar 3SAT and the set of solutions to the corresponding instance of Shakashaka.
Hence the reduction is parsimonious, and the counting version of Shakashaka is #P-complete.