講演情報
[2Yin-A-11]4値制約充足問題における遷移問題：解空間が対称な多数決演算で閉じる場合
〇弘中 創1、木村 慧1、鈴木 顕2、横尾 真1 (1. 九州大学、2. 東北大学)
キーワード：
遷移問題、制約充足問題、多数決演算
本論文では，各変数の取り得る値が0,1,2,3である4値制約充足問題における遷移問題を扱う．制約充足問題の遷移問題とは，解が2つ与えられた際に，一方の解からもう一方へ，解であることを保ちながら段階的に変換することで遷移できるか否かを判定する問題である．ここで，1度の変換においては，1つの変数への値の割当を変えることのみが許される．2値および3値制約充足問題においては，解空間が多数決演算で閉じる場合には，その遷移問題が多項式時間可解であることが，2値の場合はGopalanらとSchwerdtfegerによって，3値の場合は本論文の著者らによってそれぞれ示されている．ここで，多数決演算とは，3つの引数をもつ演算であり，2つ以上の引数の値が同じであればその値を返す演算のことを指す．変数が3値以上の場合には多数決演算は一意に定まらず，3つの引数がすべて異なる場合に返す値には任意性がある．本論文では，4値制約充足問題において，解空間が対称な多数決演算で閉じる場合に，遷移問題が多項式時間可解であることを示す．ここで多数決演算が対称であるとは，多数決演算の3つの引数の順番を入れ替えても返す値が変わらないことをいう．