Aritalab:Lecture/Algorithm/NP
Contents |
判定問題
YesかNoで答えるだけで済む問題を、判定問題または決定問題(decision problem) と呼びます。 多くの問題は、簡単に判定問題に変更できます。 何らかの数値を最適化により見つける問題であれば、例えば最適値に近い値 A を設定して
- 「その値は A より小さい（大きい）か？」
という形に問い直せばよいのです。
- 例：トラベリングセールスマン問題
有限の都市を表す集合 C = {c1, c2, ... cm} と、それらの間の距離 d(ci, cj) (整数）が定められているとします。 トラベリングセールスマン問題 (TSP: Traveling Salesman Problem) とは、「全ての都市を一度ずつ訪れるのに、最短となる道筋はどれか？」 というものです。これは判定問題ではないので、以下のように問い直します。
- 「全ての都市を一度ずつ訪れ、ある値 B より短い道筋はあるか？」
判定問題版はオリジナルの問題よりも易しくなっています。従って、判定問題にしたものが十分難しいなら、オリジナル問題はなおさら難しくなります。
- 例：答え合わせが簡単な問題と難しい問題
トラベリングセールスマン問題において、正解を知っていれば YES の答え合わせは楽ですが（具体的に道筋の総距離を計算して B より小さければよい）、NO の答え合わせは大変です。全ての道筋を検証しなくてはなりません。それに対し、例えば最短経路問題は多項式時間で最短路を見つけるアルゴリズムが知られており、アルゴリズムの正当性から、全ての道筋を検証する必要が無くなります。つまり、計算した最短路がある値 B より短いか長いかについて YES も NO も多項式時間で答えることができます。
チューリング機械
判定問題の難しさを考える際に必要なのが、チューリング機械 (TM: Turing machine) と呼ばれるコンピュータのモデルです。 チューリング機械は無限の長さを持つテープと、テープに読み書きをおこなう有限制御部から構成されます。（注： オートマトンとの根本的な違いはテープ上に自由に読み書きができる点です。） TM の本質的な部分は、テープ記号 Γ, 状態集合 Q, 状態遷移関数 δ, 入力記号 x で定義されます。
- TM = (Γ, Q, δ, x)
以下のセクションに進む前に、決定性１テープチューリング機械 (DTM: Deterministic one-tape Turing Machine) と、非決定性１テープチューリング機械 (NTDM) の概念を勉強しておいてください。
クラス P
決定性チューリング機械 (DTM) のプログラム(状態遷移関数）が、入力 x ∈ Σ* (|x| = n) に対して必要とするステップ数を考えるため、時間計算量の関数 TM(n) を用意します。
- DTM(n) = { 長さ n の入力に対してプログラムMが要するステップ数の最大値 }
この値が、ある多項式 p を用いて常に（いかなる n に対しても） TM(n) ≤ p(n) と書けるなら、M はDTMの多項式時間プログラムであると言います。
また、多項式時間で問題を解くDTMが存在する 判定問題の集合 をクラス P と言います。 クラス P に含まれるのはYES, NOで答えられる判定問題であるところに注意してください。
クラス NP
クラスNPは Non-deterministic polynomial の略で、DTMにヒントをくれる 「推測」 (guessing) モジュールを追加した TM が多項式時間内にYESと答えられる問題のクラスを意味します。このモジュールを追加した TM を、非決定性チューリング機械 (NDTM: Non-deterministic Turing machine)と呼びます （理由は以下に書きます）。
「推測」モジュールは以下の手順で作動します。
- テープに長さ |x| の入力が与えられる。
- 推測モジュールが、入力文字列を壊さないようにテープに何らかのヒント (∈ Σ*)を書き込みます。長さは何でもよく、書き込み続けて停止しなくてもOKです。
- ヒントの書き込みが停止すると、DTMと同様に通常のヘッドが起動して計算をおこないます。
- 計算の結果、状態が qY, qN にきたら停止します。このうち、 qY を受理状態とし、 qN または停止しない場合は非受理状態とします。
同じ入力 x に対してどんなヒントをもらってもよいので、計算のパターンは無限通り存在します。 そのうちいくつかが受理状態に到達する (YESと答える） と仮定しましょう。受理状態に到達する過程のなかで最小ステップ数のものを計算時間と定義します。つまり問題の各事例については、一番短い解法のステップ数を計算時間とします。 様々な入力に対する時間計算量の関数は
- NDTM(n) = { 長さ n の入力に対してプログラムMが 受理状態になるのに 要するステップ数の最大値 }
です。 この値が、ある多項式 p を用いて TM(n) ≤ p(n) と書けるとき、MをNDTMの多項式時間プログラムといいます。
NDTM は止まらなくても良い
NDTMでは、あらゆる推測 (guessing) を考慮するため、アテが外れる場合も許します。つまり、非受理状態になる計算は無視できます。 ここが DTM との一番の違いです。つまりNOと答えられなくてもよい訳です。
多項式時間でYESと答えられるNDTMが存在する 判定問題の集合 を、クラス NP と言います。 当然ですが、P に属する問題は「推測」もしないで多項式時間内に YES か NO と答えられるので、P ⊆ NP です。しかし、P が NP の真部分集合であるかどうかは、未だに証明されていません。
NPに属する問題の例
- ハミルトニアン経路問題
- 無向グラフ G(V,E) が与えられたとき、グラフの各頂点をちょうど一回ずつ通って始点に戻る閉路があるか？
頂点集合 V について正解となる頂点の並び方 (v1, v2, ... vn) をヒントとして与えられれば、ハミルトニアン経路であること (YES) が |V| 時間でわかります。
- パーティション問題
- サイズを持つ要素の集合 C を与えられたとき、C の部分集合 A で、ちょうど
- Σx ∈ A サイズ(x) = Σx ∈ (C\A) サイズ(x)
- となるものがあるか？
これも、ちょうど半分に分けられるような集合 A の要素をヒントとして与えられれば、分けられること (YES) が |C| 時間でわかります。
クラスco-NP
クラス NP は多くの問題を含むように思われますが、NPに属しない問題は否定形をとる操作で簡単に見つけられます。 たとえば
- ハミルトニアン経路問題の否定形
- 無向グラフ G(V,E) が与えられたとき、グラフの各頂点をちょうど一回ずつ通って始点に戻る閉路は全く無いか？
- パーティション問題の否定形
- サイズを持つ要素の集合 C を与えられたとき、C の部分集合 A で、ちょうどサイズを半分に分けるものは存在しないか？
これらの問題に対してYESと答えるには全ての解をしらみつぶしに探すしかなく、それには指数時間かかってしまいます。つまり、NDTM の多項式時間アルゴリズムが知られていません。上記の例は少し技巧的に思えるかもしれませんが、もっと自然な例が、素数判定問題です。
- 素数判定問題
- 自然数 n を与えられたとき、それは素数かどうか？
数 n を割り切る因数をヒントとして与えられれば素数でないことはわかりますが (NOと答えることは楽)、素数であることを示すよいヒントはなかなかありません。[1]
このように、問題の否定形がクラス NP に属す問題のクラスを co-NP といいます。「自然数 n は合成数か？」という問題はクラス NP ですし、「有向グラフはハミルトン経路を持たないか？」という問題はクラス co-NP です。クラス NP とクラス co-NP は重なりますが、全く同じ集合ではないと考えられています。（まだ証明はされていません。）
クラス P の否定形を考えてみましょう。決定性 TM の場合は、問題の否定形をとっても受理状態 qY と qN を入れ替えるだけで同じ 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の定理）、その後の計算量理論の礎を築きました。
- もくじ
参考
- ↑ 素数判定問題はクラス P に属することが証明されました。Wikipediaの記事
