Aritalab:Lecture/Algorithm/NP

決定問題

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

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

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

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

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

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

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

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

チューリングマシン

計算量理論においてコンピュータのモデルとなるのが、チューリング機械 (TM) です。 チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部から構成されます。（注： オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。） TM の本質的な部分は、テープ記号 Γ, 状態集合 Q, 状態遷移関数 δ, 入力記号 x で定義されます。

TM = (Γ, Q, δ, x)

以下のセクションに進む前に、決定性１テープチューリング機械 (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が受理状態になるのに要するステップ数の最大値 }

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

NPに属する問題の例

ハミルトニアン経路問題 

無向グラフ G(V,E) が与えられたとき、グラフの各頂点をちょうど一回ずつ通って始点に戻る閉路があるか？

頂点集合 V について正解となる頂点の並び方 (v₁, v₂, ... v_n) をヒントとして与えられれば、ハミルトニアン経路であることが |V| 時間でわかります。

パーティション問題 

サイズを持つ要素の集合 C を与えられたとき、C　の部分集合 A で、ちょうど

Σ_{x ∈ A} サイズ(x) = Σ_{x ∈ (C\A)} サイズ(x)

となるものがあるか？

これも、ちょうど半分に分けられるような集合 A の要素をヒントとして与えられれば、分けられることが |C| 時間でわかります。

co-NP

ヒントを与えられると多項式時間内でNOであることがわかっても、YESであることの判定が難しい問題も存在します。典型例が、素数判定問題です。

自然数 n を与えられたとき、それは素数かどうか？

数　n を割り切る因数をヒントとして与えられれば素数でないことはわかりますが、素数であることを示すヒントはなかなかありません。このように、問題の否定形がクラス NP に属す問題のクラスを co-NP といいます。「自然数 n は合成数か？」という問題はクラス NP ですし、「有向グラフがハミルトン経路を持たないか？」という問題はクラス co-NP です。