[3L4-GS-1] 基礎・理論：

[3L4-GS-1-03] 3値制約充足問題における遷移問題：解空間が多数決演算で閉じる場合

〇弘中 創¹、木村 慧¹、鈴木 顕²、横尾 真¹ (1. 九州大学、2. 東北大学)

キーワード：遷移問題、制約充足問題、多数決演算

本講演では，各変数の取り得る値が0,1,2である3値制約充足問題における遷移問題を扱う．制約充足問題の遷移問題とは，解が2つ与えられた際に，一方の解からもう一方へ，解であることを保ちながら段階的に変換することで遷移できるか否かを判定する問題である．ここで，一度の変換においては，1つの変数への値の割当を変えることのみが許される． 2値制約充足問題においては，解集合が多数決演算で閉じる場合には，その遷移問題が多項式時間可解であることがGopalanらおよびSchwerdtfegerによって示されている．ここで，多数決演算とは，3つの引数をもつ演算であり，2つ以上の引数の値が同じであればその値を返す演算のことを指す．また解集合が多数決演算で閉じるとは，任意の3つの解に対して，変数ごとに多数決演算を施して得られる割当がまた解になるときにいう．本講演では，2値制約充足問題に対する上記の結果を3値制約充足問題へ拡張する．このとき，多数決演算は一意に定まらず，3つの引数がすべて異なる場合に返す値には任意性があるが，どのような多数決演算で閉じている場合であっても遷移問題が多項式時間可解であることを示す．