Aritalab:Lecture/Algorithm/NP

Revision as of 13:50, 1 November 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) を用意します。

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

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

また、多項式時間で問題を解くDTMが存在する判定問題の集合をクラス P と言います。 クラス P に含まれるのは判定問題であるところに注意してください。

クラス NP

クラスNPは Nondeterministic polynomial の略で、非決定性チューリング機械という、DTMに「ヤマ張り」　(guessing) モジュールを追加した TM が多項式時間内に解くことができる問題のクラスを意味します。

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

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

同じ入力 x に対してどんなヒントをもらってもよいので、計算のパターンは無限通り存在します。 そのうちいくつかが受理状態に到達すると仮定しましょう。受理状態に到達する過程のなかで最小ステップ数のものを計算時間と定義します。つまり問題の各事例については、一番短い解法のステップ数を計算時間とします。 様々な入力に対する時間計算量の関数は

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

です。 この値が、ある多項式 p を用いて T_M(n) ≤ p(n) と書けるとき、MをNDTMの多項式時間プログラムといいます。非受理状態になる計算を無視している点がDTMの場合と違うので注意してください。

多項式時間で問題を解くNDTMが存在する判定問題の集合を、クラス NP と言います。 当然ですが、P ⊆ NP です。PがNPの真部分集合であるかどうかは、未だに知られていません。

NPに属する問題の例

ハミルトニアン経路問題 

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

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

パーティション問題 

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

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

となるものがあるか？

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

co-NP

クラス NP は多くの問題を含むように思われますが、NPに属しない問題は否定形をとる操作で簡単に見つけられます。 たとえば

ハミルトニアン経路問題の否定形 

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

パーティション問題の否定形 

サイズを持つ要素の集合 C を与えられたとき、C　の部分集合 A で、ちょうどサイズを半分に分けるものは存在しないか？

これらの問題に対する、NDTM の多項式時間アルゴリズムは知られていません。全ての解をしらみつぶしに探すしかなく、それには指数時間かかってしまいます。上記の例は少し技巧的に思えるかもしれませんが、もっと自然な例が、素数判定問題です。

素数判定問題 

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

数　n を割り切る因数をヒントとして与えられれば素数でないことはわかりますが、素数であることを示すヒントはなかなかありません。

このように、問題の否定形がクラス NP に属す問題のクラスを co-NP といいます。「自然数 n は合成数か？」という問題はクラス NP ですし、「有向グラフがハミルトン経路を持たないか？」という問題はクラス co-NP です。クラス NP とクラス co-NP は重なりますが、全く同じ集合ではないと考えられています。（まだ証明はされていません。）

クラス P の否定形を考えてみましょう。決定性 TM　の場合は、問題の否定形をとっても受理状態 q_Y と q_N を入れ替えるだけで同じ DTM が解いてしまいます。 ですから クラス P = co-P です。そしてクラス NP と、co-NP はいずれもクラスPの問題を包含します。

クラス NP完全

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

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

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