
For FullText 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
Publication
IEICE TRANSACTIONS on Fundamentals of Electronics, Communications and Computer Sciences
Vol.E86A
No.5
pp.10521060 Publication Date: 2003/05/01
Online ISSN:
DOI:
Print ISSN: 09168508 Type of Manuscript: Special Section PAPER (Special Section on Discrete Mathematics and Its Applications) Category: Keyword: computational complexity, NPcomplete, another solution, puzzle,
Full Text: PDF(282.3KB) >>Buy this Article
Summary:
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 polynomialtime transformation of solutions can derive the NPcompleteness of ASP of a certain problem from that of ASP of another. In this paper we consider nASP, the problem to find another solution when n solutions are given, and formalize it to investigate its characteristics. In particular we consider ASPcompleteness, 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 ASPcompleteness of three popular puzzles: Slither Link, Cross Sum, and Number Place. Since ASPcompleteness implies NPcompleteness, these results can be regarded as new results of NPcompleteness proof of puzzles.

