Complexity and Completeness of Finding AnotherSolution and Its Application to Puzzles

概要

論文の詳細を見る
the Another Solution Problem (ASP) of a problem II is the following problem: for a given instance ,x of II and a solution s to it, find a solution to x other than s. The potion of ASP as a now class of problems was first introduced by Ueda and Nagao. They also pointed out that 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. In this paper we consider n-ASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASP-completeness, the completeness with respect to the reductions satisfying the properties mentioned above. The complexity of ASPs has a relation with the difficulty of designing puzzles. We prove the ASP-completeness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASP-completeness implies NP-completeness, these results can be regarded as new results of NP-completeness proof of puzzles.
社団法人電子情報通信学会の論文
2003-05-01