In
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and relating these classes to each other. A computational problem is a task solved ...
and
game complexity
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.
Measures of game comp ...
, 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. A general reduction from problem
to problem
is a transformation that guarantees that whenever
has a solution
also has ''at least one'' solution and vice versa. A parsimonious reduction guarantees that for every solution of
, there exists ''a unique solution'' of
and vice versa.
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.
Formal definition
Let
be an instance of problem
. A ''Parsimonious reduction''
from problem
to problem
is a reduction such that the number of solutions to
is equal to the number of solutions to problem
.
If such a reduction exists, and if we have an oracle that counts the number of solutions to
which is an instance of
, then we can design an algorithm that counts the number of solutions to
, the corresponding instance of
. Consequently, if counting the number of solutions to the instances of
is hard, then counting the number of solutions to
must be hard as well.
Applications
Just as
many-one reduction
In computability theory and computational complexity theory, a many-one reduction (also called mapping reduction) is a reduction which converts instances of one decision problem L_1 into instances of a second decision problem L_2 where the insta ...
s are important for proving
NP-completeness
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...
, parsimonious reductions are important for proving completeness for
counting complexity classes such as
#P.
Because parsimonious reductions preserve the property of having a unique solution, they are also used in
game complexity
Combinatorial game theory has several ways of measuring game complexity. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.
Measures of game comp ...
, to show the hardness of puzzles such as
sudoku
Sudoku (; ja, 数独, sūdoku, digit-single; originally called Number Place) is a logic-based, combinatorial number-placement puzzle. In classic Sudoku, the objective is to fill a 9 × 9 grid with digits so that each column, each row ...
where the uniqueness of the solution is an important part of the definition of the puzzle.
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.
In
parameterized complexity
In computer science, parameterized complexity is a branch of computational complexity theory that focuses on classifying computational problems according to their inherent difficulty with respect to ''multiple'' parameters of the input or output. ...
, ''
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.
Polynomial-time parsimonious reductions are a special case of a more general class of reductions for counting problems, the
polynomial-time counting reduction
In the computational complexity theory of counting problem (complexity), counting problems, a polynomial-time counting reduction is a type of Reduction (complexity), reduction (a transformation from one problem to another) used to define the notion ...
s.
One common technique used in proving that a reduction
is parsimonious is to show that there is a bijection between the set of solutions to
and the set of solutions to
which guarantees that the number of solutions to both problems is the same.
Examples of parsimonious reduction in proving #P-completeness
The class #P contains the counting versions of NP decision problems. Given an instance
of an NP decision problem
the problem
asks for the number of solutions to problem
The examples of
#P-completeness below rely on the fact that #SAT is #P-complete.
#3SAT
This is the counting version of
3SAT
In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfies ...
. One can show that any boolean formula
can be rewritten as a formula in 3-
CNF form. Any valid assignment of a boolean formula is a valid assignment of the corresponding 3-CNF formula, and vice versa. Hence, this reduction preserves the number of satisfying assignments, and is a parsimonious reduction. Then, #SAT and #3SAT are counting equivalents, and #3SAT is #P-complete as well.
Planar #3SAT
This is the counting version of Planar 3SAT. The hardness reduction from 3SAT to Planar 3SAT given by Lichtenstein 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. Hence the reduction is parsimonious, and consequently Planar #3SAT is #P-complete.
Hamiltonian Cycle
The counting version of
this
This may refer to:
* ''This'', the singular proximal demonstrative pronoun
Places
* This, or ''Thinis'', an ancient city in Upper Egypt
* This, Ardennes, a commune in France
People with the surname
* Hervé This, French culinary chemist Arts, ...
problem asks for the number of Hamiltonian cycles in a given
directed graph
In mathematics, and more specifically in graph theory, a directed graph (or digraph) is a graph that is made up of a set of vertices connected by directed edges, often called arcs.
Definition
In formal terms, a directed graph is an ordered pa ...
. Seta Takahiro provided a reduction from 3SAT to this problem when restricted to planar directed max degree-3 graphs. The reduction provides a bijection between the solutions to an instance of 3SAT and the solutions to an instance of Hamiltonian Cycle in 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
Shakashaka
is a logic puzzle developed by publisher Nikoli.
Rules
Shakashaka is played on a rectangular grid of white and black squares. Some black cells may contain a number.
The objective of the puzzle is to place triangles in some of the white cells ...
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
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.
References
{{reflist
Reduction (complexity)
Combinatorial game theory