Interesting Esoterica

Complexity and Completeness of Finding Another solution and its Application to Puzzles

Article by Takayushi Yato
  • Published in 2003
  • Added on
The Another Solution Problem (ASP) of a problem $\Pi$ is the following problem: for a given instance $x$ of $\Pi$ and a solution $s$ to it, find a solution to $x$ other than $s$. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that polynomial-time parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. They used this property to show the NP-completeness of ASP of Nonogram, a sort of puzzle. Following it, Seta considered the problem to find another solution when $n$ solutions are given. (We call the problem $n$-ASP.) He proved the NP-completeness of $n$-ASP of some problems, including Cross Sum, for any $n$. In this thesis we establish a rigid formalization of $n$-ASPs to investigate their characteristics more clearly. In particular we introduce ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above, and show that ASP-completeness of a problem implies NP-completeness of $n$-ASP of the problem for all $n$. Moreover we research the relation between ASPs and other versions of problems, such as counting problems and enumeration problems, and show the equivalence of the class of problems which allow enumerations of solutions in polynomial time and the class of problems of which $n$-ASP is solvable in polynomial time. As Ueda and Nagao pointed out, the complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Number Place and Fillomino. The ASP-completeness of Slither Link is shown via a reduction from the Hamiltonian circuit problem for restricted graphs, that of Number Place is from the problem of Latin square completion, and that of Fillomino is from planar 3SAT. Since ASP=completeness implies NP-completeness as is mentioned above, these results can be regarded as new results of NP-completeness proof of puzzles.

Links

Other information

key
Yato2003
type
article
date_added
2016-06-18
date_published
2003-10-09

BibTeX entry

@article{Yato2003,
	key = {Yato2003},
	type = {article},
	title = {Complexity and Completeness of Finding Another solution and its Application to Puzzles},
	author = {Takayushi Yato},
	abstract = {The Another Solution Problem (ASP) of a problem {\$}\Pi{\$} is the following problem: for a given instance {\$}x{\$} of {\$}\Pi{\$} and a solution {\$}s{\$} to it, find a solution to {\$}x{\$} other than {\$}s{\$}. The notion of ASP as a new class of problems was first introduced by Ueda and Nagao. They also pointed out that polynomial-time parsimonious reductions which allow polynomial-time transformation of solutions can derive the NP-completeness of ASP of a certain problem from that of ASP of another. They used this property to show the NP-completeness of ASP of Nonogram, a sort of puzzle. Following it, Seta considered the problem to find another solution when {\$}n{\$}
solutions are given. (We call the problem {\$}n{\$}-ASP.) He proved the NP-completeness of {\$}n{\$}-ASP of some problems, including Cross Sum, for any {\$}n{\$}.

In this thesis we establish a rigid formalization of {\$}n{\$}-ASPs to investigate their characteristics more clearly. In particular we introduce ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above, and show that ASP-completeness of a problem implies NP-completeness of {\$}n{\$}-ASP of the problem for all {\$}n{\$}. Moreover we research the relation between ASPs and other versions of problems, such as counting problems and enumeration problems, and show the equivalence of the class of problems which allow enumerations of solutions in polynomial time and the class of problems of which {\$}n{\$}-ASP is
solvable in polynomial time.

As Ueda and Nagao pointed out, the complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Number Place and Fillomino. The ASP-completeness of Slither Link is shown via a reduction from the Hamiltonian circuit problem for restricted graphs, that of Number Place is from the problem of Latin square completion, and that of Fillomino is from planar 3SAT. Since ASP=completeness implies NP-completeness as is mentioned above, these results can be regarded as new results of NP-completeness proof of puzzles.},
	comment = {},
	date_added = {2016-06-18},
	date_published = {2003-10-09},
	urls = {http://www-imai.is.s.u-tokyo.ac.jp/{\~{}}yato/data2/MasterThesis.pdf},
	collections = {Puzzles,Basically computer science,About proof},
	url = {http://www-imai.is.s.u-tokyo.ac.jp/{\~{}}yato/data2/MasterThesis.pdf},
	urldate = {2016-06-18},
	year = 2003
}