Aritalab:Lecture/Algorithm/NP

Revision as of 21:12, 31 October 2010

判定問題

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

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

という形に問い直せばよいのです。

例

有限の都市を表す集合 C = {c₁, c₂, ... c_m} と、それらの間の距離 d(c_i, c_j) (整数）が定められているとします。 トラベリングセールスマン問題 (TSP: Traveling Salesman Problem) とは、「全ての都市を一度ずつ訪れるのに、最短となる道筋はどれか？」 というものです。これは判定問題ではないので、以下のように問い直します。

「全ての都市を一度ずつ訪れ、ある値 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に「ヤマ張り」　(guessing) モジュールを追加したチューリング機械が多項式時間内に解くことができる問題のクラスを意味します。

「ヤマ張り」モジュールは以下の手順で作動します。

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 です。

クラス NP と、co-NP はいずれもクラスPの問題を包含します。

クラス NP完全

クラス NP にはクラス P も含まれており　（真部分集合かどうかはまだわかりません）、様々な難しさの問題が含まれると予想されます。そこでクラス NP の中でも最も難しいとされる問題クラスを NP完全　(NP-complete) と定義します。

ある問題 C がNP完全であることを示すには、NPに含まれるありとあらゆる問題が C の部分問題に過ぎないことを示さなくてはなりません。これは相当難しそうです。しかし、もし一つでもNP完全問題が見つけられたとしたら、その問題を部分問題として含む問題は全てNP完全だと言えます。ですから、問題を「変換」してNP完全のクラスに入ることを証明するのは比較的簡単です。

世界で最初にNP完全問題の存在を証明する栄誉はStephen Cookに与えられました。 Cookは1971年に論理式の充足性問題がNP完全であることを証明し（Cookの定理）、その後の計算量理論の礎を築きました。