Algorithms/ExactAlgorithm - tmura's note

厳密アルゴリズム

固定パラメータ容易性

入力のサイズがで求める答えのサイズがであるとき、
計算量が（ただし、はにもにも依存しない定数）で押さえられる問題を、
固定パラメータ容易な問題と呼ぶ。

代表的な問題

論理式の充足可能性判定問題 (Satisfability Problem)

命題論理式（ブール式）が与えられて、
その充足可能性、つまりとなるような個の変数への0（偽）あるいは1（真）の
割り当て（充足解）が存在するかどうかを問う問題。通称SAT。
特に、和積標準形において全ての節のリテラル（変数またはその否定）の数が
3個以下の式に限定したSATを、3SATと呼ぶ。

3SAT問題に対するSCHアルゴリズム

変数の論理式に対して以下のステップを踏む。

1. 各変数の値として0か1かをランダムに選ぶ。
2. 現在の候補が充足解でないなら、必ず非充足の節が存在するので、その中の（３個以下の）変数から１個を選んで値をフリップして、そこに移動する。
3. 2.を回繰り返して、充足解が得られなければ1.に戻る。

3SAT問題に対するSCHアルゴリズムの性能に関する定理

3SAT問題に対して、SCHアルゴリズムは約の計算時間で、高い確率で充足解を発見する。

グラフの頂点被覆問題 (Vertex Cover Problem)

グラフの頂点被覆とは、頂点の集合であり、
グラフの各辺がその集合に含まれるいずれかの頂点に必ず接合するようなもの。

頂点被覆問題の固定パラメータ容易性に関する定理

頂点以下の頂点被覆が存在するかどうかを決定する、

およそ時間のアルゴリズムが存在する。

---

Algorithms