著者

八登 崇之 瀬田 剛広

出版者

一般社団法人情報処理学会

雑誌

情報処理学会研究報告アルゴリズム(AL) (ISSN:09196072)

巻号頁・発行日

vol.2002, no.103, pp.9-16, 2002-11-08

---

問題?に対する別解問題(ASP)というのは、?のインスタンスxとそれに対する1つの解sが与えられた時に、xのs以外の解を求める問題のことである。(新しい問題クラスとしてのASPの概念はUedaとNagaoによる。)本論文ではn個の解が与えられたときにもう1つの解を求める問題(n-ASP)について考察する。特に、対応する解への変換も多項式時間で行えるような多項式時間parsimonious還元に関する完全性であるASP完全性について考察する。応用として、本論文では3つの有名なパズル、スリザーリンクとカックロ(クロスサム)とナンバープレース(数独)についてそのASP換算製(NP完全性を含意する)を示す。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 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 of solutions. As an application, we prove the ASP-completeness (which implies NP-completeness) of three popular puzzles: Slither Link, Cross Sum, and Number Place.