• 作成日時:
  • 更新日時:

計算理論(P vs NP問題,NP完全性)

P vs NP問題

これまでにPはその言語に属しているかどうかを多項式時間で判定できる言語のクラス,NPはその言語に属してことを多項式時間で検証できる言語のクラスだと学んできた.

P ≠ NPだと多くの人が県警から信じているが,実際にPに属していないNPの言語は見つかっていない.多項式時間で判定できないことを証明するのは難しい.もしかしたら良いアルゴリズムが存在するかもしれない.

NP完全性

NPに属する問題の中で最も難しい問題を見つけようというアプローチ.この最も難しい問題をNP完全問題と呼ぶ.

NP完全問題は最も難しい問題なのでPに属さないことを証明するのが比較的容易なはず.逆に,最も難しい問題であるNP完全問題がPに属すればP = NPとなることがわかる.

多項式時間帰着可能性

問題Aへの入力を問題Bへの入力に変換することを考える.この変換(帰着という)が存在するならば,問題Bを解くアルゴリズムを用いて,問題Aも解けることになる.Aへの任意の入力を帰着を用いてBへの入力へと変換し,Bを解くアルゴリズムに入力すれば問題を解くことが可能.

例えば,長方形の面積を求める問題は,辺の高さと幅を求める問題に帰着可能.連立方程式を解く問題は,逆行列を求める問題へと帰着可能.

多項式時間計算可能関数

任意の入力\(w\)に対してテープに\(f(w)\)だけを書き込んで停止し,その動作時間は多項式時間であるようなTuring機械が存在するとき,関数fは多項式時間計算可能関数であるという.

多項式時間帰着可能

言語Aと言語Bに対して,多項式時間計算可能\(f\)が存在して,全ての\(w\)について\(w ∈ A ⇔ f(w) ∈ B\)であるとき,\(A ≦_p B\)と書き,言語Aが言語Bに多項式時間帰着可能であるという.

NP完全

次の条件を満たすBをNP完全という.

  1. \(B ∈ NP\)
  2. NPに属する全てのAが,Bに多項式時間帰着可能である

わかりやすく言うと,NPに属する全ての問題はNP完全よりも同等か優しい.ということ.

彩色問題

4色問題の紹介.どう計算理論と絡んでくるのかよくわからない.

Welsh-Powellのアルゴリズムの記憶を思い出した.

  1. グラフGの節点の次数を全て求める
  2. 節点を次数の多い順に,色1の節点と隣り合ってなければ色1で塗る
  3. 塗り終わったら2を色2,色3,色4と繰り返す
  4. 全て塗り終わったら終了
Welsh-Powellのアルゴリズムでの彩色例
Welsh-Powellのアルゴリズムでの彩色例