はてぃーぽったーの備忘録

某授業まとめ+競プロの感想記事

PとNPのお話および多項式時間還元について(第10回スライド参照)

クラスPとNPについてのお話を試験前最後の記事とさせていただきます。

まず、クラスとは何か。しっかりと定義するのはとてもこの1記事では収まり切りません。そのため、「クラスはものの集まり」程度に思っておいてくれるといいかな、と思います。（あくまで集合とは違うのですが、今回のお話ではそう思っても差支えないと思います）

 

次に、PとNPのお話に入る前に二つの表現形式を定義しておきます。TIME(t(n))とNTIME(t(n))についてです。

t: N → R^{+}を関数とし、

    TIME(t(n))=\{L| LはO(t(n))時間のTMで判定可能な言語\}

NTIME(t(n))=\{L| LはO(t(n))時間の非決定性TMで判定可能な言語\}

では、Pとは何でしょうか。教科書の定義を活用させていただくと、

 

Pを決定性単一テープTMによって多項式時間で判定できる言語のクラスとする。すなわち

  P = \cup_{k}TIME(n^k)

 

じゃあNPは非決定性単一テープTMで…？と思うかもしれませんが今回はそう定義しません。NPを定義するために、検証装置というものを定義します。

まず、検証とはどのようなものか例を交えて説明します。ハミルトン経路問題というものが存在します。これは有向グラフGとその節点s,tに対してグラフの全ての節点を一度だけ通ることを条件にsからtに向かう経路があるかどうかを判定するという問題です。単純にこの問題を解くとすると、指数時間アルゴリズムによる解法で挑むことになると思います。ハミルトン経路があるかどうか分からない状態では、sからtへの経路を全探索する必要があるからです。

一方、sからtに向かう経路が1つ与えられた時、その経路長をnとすれば、O(n)ステップでその経路をもとにそれがハミルトン経路であるか確かめる（検証する）ことができます。

以上のような考えのもと、多項式時間検証装置と呼ばれるものを定義します。

 

アルゴリズムVに対して言語Aを次のように定義できるとき、VをAの検証装置という。

A = {w| Vは、ある文字列cに対して<w,c>を受理}

 

検証装置の計算時間はwの長さについてのみ測ります。したがって、多項式時間検証装置とはwの長さに対して多項式時間でcの検証を行うアルゴリズムとなります。言語Aが多項式時間検証装置を持つとき、Aは多項式時間検証可能であると言います。

この多項式時間検証装置をもとにNPが定義されます。

 

NPは多項式時間検証装置を持つ言語のクラスである。

 

ただ、結局のところこれは次と同じことを言っています。

NPを非決定性TMによって多項式時間で判定できる言語のクラスとする。すなわち

NP = \cup_{k}NTIME(n^k)

 

さて、これでPとNPの定義が完了しました。分かりにくかったら申し訳ないのですが、少しでも頭が整理できたならば幸いです。

 

最後に、多項式時間還元のお話をします。これは問題AがPに属することを、Pに属する問題Bを利用して示すのに役立ちます。

多項式時間で計算可能な関数f : \Sigma^{*} → \Sigma^{*}を考え、言語AとBに対し、全ての w \in Aで以下の事柄が成り立つとします。

w \in A \leftrightarrow f(w) \in B

この時、 A \leq _{P}Bと書き、言語Aが言語Bに多項式時間還元可能であるといいます。では、以下の例題を解いてみようと思います。

 

Q. A \leq _{P}B, B \in Pならば A \in Pであることを示せ。

A. 示したい事柄は、Aを多項式時間で判定するアルゴリズムNが存在することである。 B \in Pより、Bを多項式時間で判定するアルゴリズムMが存在する。このとき、次のようにAを判定する多項式時間アルゴリズムNを構成する。

N = 「入力wに対して、

1. f(w)を計算する(多項式時間)

2. f(w)に対してMを動作させ(多項式時間)、その出力をそのまま出力する。」

\forall w \in A \leftrightarrow f(w) \in Bなので、Mが受理すればNも受理、Mが拒絶すればNも拒絶とすることでNはAを判定する。したがって、あとはNが多項式時間で作動することを示せばよいが、f(w)は精々wの長さに対する多項式程度の長さしかなく、それについて多項式時間のアルゴリズムMを動作させているのでNは多項式時間で動作する。したがってA \in Pである。

 

ではでは、マサカリが飛んでくるまでは一先ずこれで最後の編集とさせていただきます。皆さんテスト頑張ってください。