SE Can't Code

A Tokyo based Software Engineer. Not System Engineer :(

NP完全性について.

NP完全性について勉強したのでまとめる。今回は妙にコンピュータサイエンスちっくな話。

TL;DR


まず全ての問題に効率的なアルゴリズムが存在するとは限らない。指数関数的に膨大な計算量を必要とする問題も存在する。ざっくりと効率性という観点から問題を二つに分けると、多項式時間で効率的に解ける問題指数時間かかってしまう問題に分類出来る。この二つの分類の間に多くの宙に浮いた問題が多数あり、どちらに属するかがわからないことがある。それらをNP完全問題(NP-complete problem)と扱うことが出来れば非常に便利と言える。

問題の難しさ


問題には下記のような難易度がある。

  • コンピュータで解けない問題 (Ex: Halting Problem)
  • 指数時間で解ける問題 (Ex: Generalized Checkers)
  • 多項式時間で解ける問題 (Ex: Shortest Path)
  • 線形時間で解ける問題 (Ex: Graph Connectivity)

問題の難しさを測るには、計算複雑性理論が重要になる。一般的に問題の難しさを出すにはアルゴリズムの実行時間や計算量を元にする。その際にオーダやビッグシータを用いて計算を行うが、これらは問題の複雑性の上限を決めているに過ぎず、下限を算出する必要がある。上限と下限を決定してあげることで、問題の難しさがどの程度のものかわかるようになる。

NP問題(Non-deterministic Polynomial time decidable problems)


NPの定義は次の3つである、ただしこれらはお互い同値であることが証明されている。

  • 非決定性チューリングマシンによって多項式時間で解ける問題。
  • yes となる証拠が与えられたとき、その証拠が本当に正しいかどうかを多項式時間で判定できる問題。
  • 問題の探索状態を木で表したとき、yes にたどり着く最短距離が問題のサイズの多項式に比例する問題。


非決定性チューリングマシンとは、正規表現ロジックのオートマトンをイメージするとわかりやすいが、今いる状態から次の状態に行く選択肢が複数あった時に常に解に近づく選択肢を選べる機械である。

NPをざっくり表現すると、非決定性の要素がある多項式時間を使えば解くことができる問題と言える。
NPを考える時に重要な要素として、受け入れられる証明の簡潔さと素早い検証アルゴリズムの二つの条件がある。受け入れられる証明とは、決定問題の答えがYESとなるような情報のこと、そして素早い検証アルゴリズムとは多項式時間で解くことが出来るかどうかの調査のことを指す。つまり、NPとは証明が与えられた時、多項式時間で解くことが出来る問題であればNPと言うことができる。ちなみに、Pは証明が無くとも多項式時間で解くことが出来る問題であり、多項式時間で判定可能な問題は多項式時間で検証可能であるので、P⊆NPであると言える。

NP困難とNP完全


NPの全問題から多項式時間帰着される問題をNP困難と呼ぶ。また、なんらかのNP困難問題から問題Xへ還元することが出来れば問題XはNP困難問題と言える。つまり、問題Xの答えをNP困難問題を解くために利用することが可能となり、問題Xは少なくともNP困難問題と同じくらいに難しい必要がある。
NP困難問題の中でも有名な問題としてが充足可能性問題(SAT問題)というものがある。
Boolean satisfiability problem - Wikipedia, the free encyclopedia


NP完全問題は、NP困難かつそれ自体がNPであるような問題と呼ぶ。つまりはこの問題がNPの中で最も難しく、これが多項式時間で解ければNPの問題はすべて解けるということになる。
なお、NP完全問題は世の中に沢山あり、以下のWikipediaのリストにまとめられている。

List of NP-complete problems - Wikipedia, the free encyclopedia


以上、ざっくりとNP完全性についてまとめたが、なかなか難しくて理解するのにかなり時間がかかった(というか認識間違いが無いかすごい不安)。改めて僕は理論的なところが苦手だなぁと思った。今他に勉強しているところとして、サンプルサイズを算出するための検定理論を頑張っているんだけれど、これもなかなか前へ進まない。
大学行ってコンピュータサイエンス統計学を学びたいなぁ。ああ

Remove all ads