Parsimonious reduction
Notion in computational complexity theory / From Wikipedia, the free encyclopedia
Dear Wikiwand AI, let's keep it short by simply answering these key questions:
Can you list the top facts and stats about Parsimonious reduction?
Summarize this article for a 10 year old
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. 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.