1. References

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.

More formally,

parsimonious reductions are defined for problems in nondeterministic complexity classes such as NP,

which are defined by a verifier algorithm whose input is a pair of strings (an instance of the problem and a candidate solution) and whose output is true when the candidate solution is a valid solution of the instance.

For example, in the Boolean satisfiability problem, the instance might be a Boolean expression and the candidate solution might be a truth assignment to its variables; a valid truth assignment is one that makes the expression evaluate to true.

A parsimonious reduction from one problem X of this type to another problem Y is an algorithmic transformation from instances of X to instances of Y

such that the number of solutions of an instance of X equals the number of solutions of the transformed instance of Y.^[1]

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]

References

• Iliana Douglas
• Iliana Nikolova
• Ilian Efremov
• Ilian Evtimov
• Ilian Garnet
• Ilian Micanski
• Ilian Mitsanski
• Ilia Prefecture
• Ilias Alexandru
• Ilias Anastasakos
• Ilia Saveliev
• Ilias Bej Vrioni
• Ilias Bey Vrioni
• Ilias Colceag
• Ilias Georgopoulos
• Ilias Gorchkhanov
• Ilia Shiolashvili
• Iliash Kolchak
• Ilia Shtemler
• Ilias Iliou
• Ilias Ioannou
• Ilias Lalaounis Jewelery Museum
• Ilias Lalaounis Jewelry Museum
• Ilias Louka
• Ilias Manikas