Aritalab:Lecture/Algorithm/NP

決定問題

YesかNoで答えるだけで済む問題を、決定問題 (decision problem) と呼びます。 世の中の問題を決定問題にするのは簡単です。 何らかの数値を最適化により見つける問題であれば、例えば最適値に近い値 A を設定して

その値は A より小さい（大きい）か？

という形で問い直せば、決定問題になります。

例 トラベリングセールスマン

有限の都市を表す集合 C = {c₁, c₂, ... c_m} と、それらの間の距離 d(c_i, c_j) (整数）が定められているとします。

オリジナルの問い 「全ての都市を一度ずつ訪れるのに、最短となる道筋はどれか？」

決定問題の問い　「全ての都市を一度ずつ訪れ、ある値 B より短い道筋はあるか？」

決定問題版はオリジナルの問題をいくぶん易しくしています。決定問題版でも十分難しいなら、オリジナルはなおさら難しいことが言えそうです。

チューリングマシン

計算量理論においてコンピュータのモデルとなるのが、チューリング機械 (TM) です。 チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部から構成されます。（注： オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。）

TM　のページにある、決定性１テープチューリング機械 (DTM: Deterministic one-tape Turing Machine) と、非決定性１テープチューリング機械　(NTDM) の概念を勉強しておいてください。

クラス P

DTMのプログラムが、あらゆる入力 x ∈ Σ^* (|x| = n) に対して要するステップ数を考えるため、時間計算量の関数 T_M(n) を用意します。

T_M(n) = { 長さ n の入力に対してプログラムMが要するステップ数の最大値 }

この値が、ある多項式 p を用いて T_M(n) ≤ p(n) と書けるなら、M はDTMの多項式時間プログラムであると言います。

また、多項式時間で問題を解くDTMが存在する問題の集合をクラス P と言います。

クラス NP

ここでは簡単な概念を説明します。クラスNPは Nondeterministic polynomial の略で、NDTMという、DTMに「ヤマ張り」モジュールを追加したチューリングマシンを考えます。 NDTMは通常のヘッドに加え、NPは「ヤマ張りヘッド」を持っており、以下の手順で作動します。

1. テープに長さ |x| の入力が与えられる。
2. ヤマ張りヘッドが、入力文字列を壊さないようにテープに何らかの文字列 (∈ Σ^*)を書き込みます。長さは何でもよく、書き込み続けて停止しなくてもOKです。
3. 　ヤマ張りヘッドが停止する場合に限り、DTMと同様に通常のヘッドが起動して計算をおこないます。
4. 状態が q_Y, q_N にきたら停止します。このうち、 q_Y を受理状態とし、 q_N または停止しない場合は非受理状態とします。

こうすると、入力 x に対する計算のバリエーションは無限通り存在します。 そのうちいくつかが受理状態に到達すると仮定します。受理状態に到達する過程のなかで最小ステップ数のものが、計算時間に相当します。 時間計算量の関数は

TM(n) = { 長さ n の入力に対してプログラムMが受理状態になるのに要するステップ数の最大値 }

と定義します。 ここで非受理状態になる計算は無視している点に注意してください。