Aritalab:Lecture/Algorithm/NP - Revision history

Adm: /* クラス NP */

2017-08-04T04:47:11Z

‎クラス NP

Adm at 01:50, 29 July 2013

2013-07-29T01:50:55Z

Adm: /* クラスco-NP */

2012-01-04T16:33:09Z

‎クラスco-NP

Adm: /* co-NP */

2012-01-04T16:31:53Z

‎co-NP

Adm: /* 判定問題 */

2011-10-25T02:51:23Z

‎判定問題

Adm: /* 判定問題 */

2011-10-25T02:50:26Z

‎判定問題

Adm: /* クラス NP完全 */

2011-10-18T01:51:30Z

‎クラス NP完全

Adm: /* クラス NP完全 */

2011-10-14T00:01:04Z

‎クラス NP完全

Adm: /* クラス P */

2011-10-06T02:11:28Z

‎クラス P

Adm: /* クラス NP完全 */

2011-10-06T02:10:54Z

‎クラス NP完全

@@ Line 35: / Line 35: @@
 ==クラス NP==
-クラスNPは Non-deterministic polynomial の略で、DTMにヒントをくれる 「ヤマ張り」　(guessing) モジュールを追加した TM が多項式時間内にYESと答えられる問題のクラスを意味します。このモジュールを追加した TM を、非決定性チューリング機械 (NDTM: Non-deterministic Turing machine)と呼びます　（理由は以下に書きます）。
+クラスNPは Non-deterministic polynomial の略で、DTMにヒントをくれる 「推測」　(guessing) モジュールを追加した TM が多項式時間内にYESと答えられる問題のクラスを意味します。このモジュールを追加した TM を、非決定性チューリング機械 (NDTM: Non-deterministic Turing machine)と呼びます　（理由は以下に書きます）。
-「ヤマ張り」モジュールは以下の手順で作動します。
+「推測」モジュールは以下の手順で作動します。
 # テープに長さ |x| の入力が与えられる。
-# ヤマ張りモジュールが、入力文字列を壊さないようにテープに何らかのヒント (&isin; &Sigma;<sup>*</sup>)を書き込みます。長さは何でもよく、書き込み続けて停止しなくてもOKです。
+# 推測モジュールが、入力文字列を壊さないようにテープに何らかのヒント (&isin; &Sigma;<sup>*</sup>)を書き込みます。長さは何でもよく、書き込み続けて停止しなくてもOKです。
 #　ヒントの書き込みが停止すると、DTMと同様に通常のヘッドが起動して計算をおこないます。
 # 計算の結果、状態が q<sub>Y</sub>, q<sub>N</sub> にきたら停止します。このうち、 q<sub>Y</sub> を受理状態とし、 q<sub>N</sub> または停止しない場合は非受理状態とします。
@@ Line 51: / Line 51: @@
 ===NDTM は止まらなくても良い===
-NDTMでは、あらゆるヒント (guessing) を考慮するため、ヤマが外れる場合も許します。つまり、非受理状態になる計算は無視できます。
+NDTMでは、あらゆる推測 (guessing) を考慮するため、アテが外れる場合も許します。つまり、非受理状態になる計算は無視できます。
 ここが DTM との一番の違いです。つまりNOと答えられなくてもよい訳です。
 多項式時間でYESと答えられるNDTMが存在する '''判定問題の集合''' を、クラス NP と言います。
-当然ですが、P に属する問題は「ヤマ張り」もしないで多項式時間内に YES か NO と答えられるので、P &sube; NP です。しかし、P が NP の真部分集合であるかどうかは、未だに証明されていません。
+当然ですが、P に属する問題は「推測」もしないで多項式時間内に YES か NO と答えられるので、P &sube; NP です。しかし、P が NP の真部分集合であるかどうかは、未だに証明されていません。
 ===NPに属する問題の例===

@@ Line 75: / Line 75: @@
 ; 素数判定問題 : 自然数 n を与えられたとき、それは素数かどうか？
-数　n を割り切る因数をヒントとして与えられれば素数でないことはわかりますが (NOと答えることは楽)、素数であることを示すよいヒントはなかなかありません。<ref>素数はネイ問題はクラス P に属することが証明されました。</ref>
+数　n を割り切る因数をヒントとして与えられれば素数でないことはわかりますが (NOと答えることは楽)、素数であることを示すよいヒントはなかなかありません。<ref>素数判定問題はクラス P に属することが証明されました。[http://ja.wikipedia.org/wiki/AKS%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95 Wikipediaの記事]</ref>
 このように、問題の否定形がクラス NP に属す問題のクラスを co-NP といいます。「自然数 n は合成数か？」という問題はクラス NP ですし、「有向グラフはハミルトン経路を持たないか？」という問題はクラス co-NP です。クラス NP とクラス co-NP は重なりますが、全く同じ集合ではないと考えられています。（まだ証明はされていません。）

@@ Line 67: / Line 67: @@
 これも、ちょうど半分に分けられるような集合 A の要素をヒントとして与えられれば、分けられること (YES) が |C| 時間でわかります。
-===クラスco-NP===
+==クラスco-NP==
 クラス NP は多くの問題を含むように思われますが、NPに属しない問題は否定形をとる操作で簡単に見つけられます。
 たとえば

@@ Line 67: / Line 67: @@
 これも、ちょうど半分に分けられるような集合 A の要素をヒントとして与えられれば、分けられること (YES) が |C| 時間でわかります。
-===co-NP===
+===クラスco-NP===
 クラス NP は多くの問題を含むように思われますが、NPに属しない問題は否定形をとる操作で簡単に見つけられます。
 たとえば

@@ Line 15: / Line 15: @@
 ; 例：答え合わせが簡単な問題と難しい問題
-トラベリングセールスマン問題において、正解を知っていれば YES の答え合わせは楽ですが（具体的に道筋の総距離を計算して B より小さければよい）、NO の答え合わせは大変です。全ての道筋を検証しなくてはなりません。それに対し、例えば最短経路問題は多項式時間で最短路を見つけるアルゴリズムが知られており、その正当性から、全ての道筋を検証する必要が無くなります。つまり、最短路がある値 B より短いか長いかについて YES も NO も多項式時間で答えることができます。
+トラベリングセールスマン問題において、正解を知っていれば YES の答え合わせは楽ですが（具体的に道筋の総距離を計算して B より小さければよい）、NO の答え合わせは大変です。全ての道筋を検証しなくてはなりません。それに対し、例えば最短経路問題は多項式時間で最短路を見つけるアルゴリズムが知られており、アルゴリズムの正当性から、全ての道筋を検証する必要が無くなります。つまり、計算した最短路がある値 B より短いか長いかについて YES も NO も多項式時間で答えることができます。
 ==チューリング機械==

@@ Line 6: / Line 6: @@
 という形に問い直せばよいのです。
-;例
+;例：トラベリングセールスマン問題
 有限の都市を表す集合 C = {c<sub>1</sub>,  c<sub>2</sub>,  ... c<sub>m</sub>} と、それらの間の距離 d(c<sub>i</sub>,  c<sub>j</sub>) (整数）が定められているとします。
 トラベリングセールスマン問題 (TSP: Traveling Salesman Problem) とは、「全ての都市を一度ずつ訪れるのに、最短となる道筋はどれか？」
@@ Line 12: / Line 12: @@
 :「全ての都市を一度ずつ訪れ、ある値 B より短い道筋はあるか？」
-判定問題版はオリジナルの問題よりも易しくなっています。従って、判定問題にしたものでも十分難しいなら、オリジナル問題はなおさら難しくなります。
+判定問題版はオリジナルの問題よりも易しくなっています。従って、判定問題にしたものが十分難しいなら、オリジナル問題はなおさら難しくなります。
 ==チューリング機械==

@@ Line 89: / Line 89: @@
 ;もくじ
-{{GenerateIndex|Aritalab|Lecture/Algorithm/CooksTheorem}}{{GenerateIndex|Aritalab|Lecture/Algorithm/Reducibility}}{{GenerateIndex|Aritalab|Lecture/Algorithm/Reducibility2}}
+{{GenerateIndex|Aritalab|Lecture/Algorithm/CooksTheorem}}{{GenerateIndex|Aritalab|Lecture/Algorithm/Reducibility}}
 ===参考===
 <references/>

@@ Line 28: / Line 28: @@
 この値が、ある多項式 p を用いて常に（いかなる n に対しても） T<sub>M</sub>(n) &le; p(n) と書けるなら、M はDTMの多項式時間プログラムであると言います。
-また、多項式時間で問題を解くDTMが存在する「判定問題の集合」をクラス P と言います。
+また、多項式時間で問題を解くDTMが存在する '''判定問題の集合''' をクラス P と言います。
 クラス P に含まれるのはYES, NOで答えられる判定問題であるところに注意してください。

← Older revision		Revision as of 02:10, 6 October 2011
Line 87:		Line 87:
	世界で最初にNP完全問題の存在を証明する栄誉はStephen Cookに与えられました。		世界で最初にNP完全問題の存在を証明する栄誉はStephen Cookに与えられました。
	Cookは1971年に[[Aritalab:Lecture/Algorithm/CooksTheorem\|論理式の充足性問題がNP完全である]]ことを証明し（Cookの定理）、その後の計算量理論の礎を築きました。		Cookは1971年に[[Aritalab:Lecture/Algorithm/CooksTheorem\|論理式の充足性問題がNP完全である]]ことを証明し（Cookの定理）、その後の計算量理論の礎を築きました。
		+
		+
		+	===参考===
		+	<references/>