For faster navigation, this Iframe is preloading the Wikiwand page for Parsimonious reduction.

Parsimonious reduction

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.

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 .[1] 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 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 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. 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[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. Hence the reduction is parsimonious, and consequently Planar #3SAT is #P-complete.

Hamiltonian Cycle

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. 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 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.

References

  1. ^ a b c Goldreich, Oded (2008), Computational Complexity: A Conceptual Perspective, Cambridge University Press, pp. 203–204, ISBN 9781139472746
  2. ^ Yato, Takayuki; Seta, Takahiro (2003), "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles", IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A (5): 1052–1060
  3. ^ Flum, J.; Grohe, M. (2006), Parameterized Complexity Theory, EATCS Texts in Theoretical Computer Science, Springer, p. 363, ISBN 9783540299530
  4. ^ Gomes, Carla P.; Sabharwal, Ashish; Selman, Bart (2009), "Chapter 20. Model Counting", in Biere, Armin; Heule, Marijn; van Maaren, Hans; Walsh, Toby (eds.), Handbook of Satisfiability (PDF), Frontiers in Artificial Intelligence and Applications, vol. 185, IOS Press, pp. 633–654, ISBN 9781586039295. See in particular pp. 634–635.
  5. ^ Lichtenstein, David (May 1982). "Planar Formulae and Their Uses". SIAM Journal on Computing. 11 (2): 329–343. doi:10.1137/0211025. ISSN 0097-5397.
  6. ^ Seta, Takahiro (2001). The Complexities of Puzzles, Cross Sum, and their Another Solution Problems (ASP). CiteSeerX 10.1.1.81.7891.
  7. ^ "JAIST Repository: Computational complexity and an integer programming model of Shakashaka". dspace.jaist.ac.jp. Retrieved 2019-05-15.
{{bottomLinkPreText}} {{bottomLinkText}}
Parsimonious reduction
Listen to this article

This browser is not supported by Wikiwand :(
Wikiwand requires a browser with modern capabilities in order to provide you with the best reading experience.
Please download and use one of the following browsers:

This article was just edited, click to reload
This article has been deleted on Wikipedia (Why?)

Back to homepage

Please click Add in the dialog above
Please click Allow in the top-left corner,
then click Install Now in the dialog
Please click Open in the download dialog,
then click Install
Please click the "Downloads" icon in the Safari toolbar, open the first download in the list,
then click Install
{{::$root.activation.text}}

Install Wikiwand

Install on Chrome Install on Firefox
Don't forget to rate us

Tell your friends about Wikiwand!

Gmail Facebook Twitter Link

Enjoying Wikiwand?

Tell your friends and spread the love:
Share on Gmail Share on Facebook Share on Twitter Share on Buffer

Our magic isn't perfect

You can help our automatic cover photo selection by reporting an unsuitable photo.

This photo is visually disturbing This photo is not a good choice

Thank you for helping!


Your input will affect cover photo selection, along with input from other users.

X

Get ready for Wikiwand 2.0 ๐ŸŽ‰! the new version arrives on September 1st! Don't want to wait?