Complexity and Completeness of Finding Another Solution and Its Application to Puzzles
Takayuki Yato, Takahiro Seta · 2003
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.) In this paper we consider n-ASP, the problem to find another solution when n solutions are given. In particular we consider ASP-completeness, the completeness with respect to the parsimonious reductions which allow polynomial-time transformation