For Full-Text PDF, please login, if you are a member of IEICE,|
or go to Pay Per View on menu list, if you are a nonmember of IEICE.
Complexity and Completeness of Finding Another Solution and Its Application to Puzzles
Takayuki YATO Takahiro SETA
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Publication Date: 2003/05/01
Print ISSN: 0916-8508
Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications)
computational complexity, NP-complete, another solution, puzzle,
Full Text: PDF(282.3KB)>>
The Another Solution Problem (ASP) of a problem is the following problem: for a given instance x of 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 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.