目次 (Chapter 1)
1. イントロダクション
2. 問題,アルゴリズム,複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. NP完全問題
6. この本の概略
証明可能な“intractable”な問題
• ‘‘intractable’’な問題の存在
– “undecidable”な問題
– “nondeterministically”な問題
“intractable”な問題の存在
• “intractable”な問題(多項式時間アルゴリズム
では解けない問題)は実際に存在するか?
• 問題が“intractable”となる要因:
– 問題が難しすぎて、解を求めるのに指数関数時
間必要である。
– 解自身が大きすぎて、入力長の多項式関数で抑
えられた長さの表現では記述できない。
“intractable”な問題の存在
• 解が大きすぎる問題:
例: 巡回セールスマン問題の変形
• インスタンスに追加パラメータ B を持たせる。
• 「長さが B 以下のすべての巡回路を求めよ」
• この問題に対して、指数的に多くの巡回路が B 以下
の長さを持つように、インスタンスを構成可能。
• すなわち、解を全て書き出すことのできる多項式時間
アルゴリズムは存在しない。⇒“intractable”
しかし、このような問題は非現実的である。
• 我々が関心を向けるのは、一つめの要因に
絞られる。
“undecidable”な問題
• “undecidable”な問題:
– その問題を解くアルゴリズムが存在しない問題
• 1936年,アラン・チューリング
– 「任意のコンピュータプログラムと、そのプログラ
ムへの任意の入力が与えられたとき、そのプログ
ラムが有限時間内で停止するか否かを判定せ
よ」
– この問題を解くことのできるアルゴリズムは存在
しないことを示した。
“undecidable”な問題
• 現在、様々な“undecidable”な問題が知られてい
る:
– 有限表現群に関する自明な問題 [Rabin,1958]
– ヒルベルトの第十問題(整数上の多項式の解決可能性)
[Matijasevic,1970]
– “Tiling the plane”の問題 [Berger,1966]
• これらの問題は、どんなアルゴリズムでも(ましてや
多項式時間アルゴリズムなんかでは到底!)解けな
いので、強い意味で“intractable”である。
“nondeterministically”な問題
• “decidable”な(すなわち、“undecidable”でない)問題
の中に、“intractable”な問題を最初に見つけたの
は、Hartmains と Stearns [1965] であった。
• しかし、彼らの結果は、非常に特別な性質を持つ、
「人工的な」問題に限られていた。
• これに対して、「自然な」“decidable”問題のうちで
“intractable”な問題は、 Meyer と Stockmeyer
[1972],Fischer とRabin [1974]によって与えられた。
• これらの問題は、現在“nondeterministically”な問
題として類別されている。
“nondeterministically”な問題
• “nondeterministically”な問題:
– “nondeterministic”コンピュータモデルでは、多項式時
間では解けない問題
• “nondeterministic”コンピュータモデル:
– 無限個の独立な計算を、並列に追跡する能力を持つ計算
機モデル
• 注: “nondeterministic”コンピュータモデルは、
“reasonable”な計算機モデルではないが、NP完全
性の理論において重要な役割を担っている。
(Chapter 2 で詳しく説明)
証明可能な“intractable”な問題
(まとめ)
• 現在知られている“intractable”な問題は、
– “undecidable”な問題
– “nondeterministically”な問題
のどちらかである。
• もし、このどちらかであることを示すことができれば、
問題が“intractable”であることを証明できる。
• しかしながら、実際に遭遇する、一見“intractable”
に見える問題の多くは、上のどちらにも属さない。
目次 (Chapter 1)
1. イントロダクション
2. 問題,アルゴリズム,複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. NP完全問題
6. この本の概略
NP完全問題
• 問題の間の相関関係
• NP完全性の理論(Cook の論文)
NP完全問題
• 問題の間の相関関係
– 帰着 (reducing)
• NP完全性の理論(Cook の論文)
問題の間の相関関係
• 問題と問題の間にある関係は、アルゴリズムデザイ
ナーに有用な情報を提供する。
• 二つの問題の間に関係があることを示すときに、
「帰着」という概念がよく使われる。
• 問題 A を問題 B へ帰着 (reducing) するとは:
– A の任意のインスタンスから等価な B のインス
タンスへの構成的な変換(写像)を与えること。
– このような変換は、 B を解くアルゴリズムを A を
解くアルゴリズムに変換する方法を与える。
帰着 (reducing)
問題 A
問題 B
インスタンス
の集合
インスタンス
の集合
?
アルゴリズム
アルゴリズム
解
解
帰着 (reducing)
問題 A
問題 B
問題 B が解ければ、
問題 A も解ける。
これらの問題のうち、1つで
も解ければ、他のすべての 問題1
問題も解ける。
問題2
問題3
⇒同じ難しさの問題
問題5
問題4
NP完全問題
• 問題の間の相関関係
• NP完全性の理論(Cook の論文)
– 多項式時間帰着可能性
– クラスNP
– 充足可能性問題
– NP完全問題
NP完全性の理論
• NP完全性の理論の基盤は、1971年に提出された
Stephen Cook の論文:
“The Complexity of Theorem Proving Procedures”
に用意されていた。
• Cook は、まず多項式時間帰着可能性に注目した。
• 多項式時間帰着可能:
– 帰着に要求される変換が、多項式時間アルゴリ
ズムによって実行できること
多項式時間帰着可能性
(Polynomial Time Reducibility)
問題 A
インスタンス
の集合
多項式時間
アルゴリズム
変換
多項式時間
アルゴリズム
変換
解
問題 B
インスタンス
の集合
アルゴリズム
解
多項式時間帰着可能性
(Polynomial Time Reducibility)
• 問題 A が問題 B へ多項式時間帰着可能であり、
問題 B に対する多項式時間アルゴリズムが存在す
るとき、問題 A を解く多項式時間アルゴリズムの存
在がいえる。
多項式時間帰着可能性
(Polynomial Time Reducibility)
問題 A
インスタンス
の集合
問題 B
多項式時間
アルゴリズム
インスタンス
の集合
多項式時間
アルゴリズム
解
多項式時間
アルゴリズム
解
クラスNP (Class NP)
• 次に Cook が注目したのは、クラスNPであった。
• クラスNP:
– “nondeterministic”コンピュータ上で、多項式時
間で解くことのできる判定問題のクラス
– 判定問題: 解が“yes”か“no”である問題
• 実際に遭遇する“intractable”に見える問題は、判
定問題に言い換えたとき、このクラスに属する。
クラスNP (Class NP)
判定問題
クラスNP
“undecidable”な問題
“nondeterministically”な問題
“intractable”
充足可能性問題
(Satisfiability Problem)
• 充足可能性問題は、クラスNPに属する問題の一つ
である。
• Cook は、次のことを証明した:
– クラスNPに属するすべての問題は、充足可能性
問題に多項式時間帰着可能である。
– すなわち、充足可能性問題を解く多項式時間ア
ルゴリズムが存在するならば、NPに属するすべ
ての問題には、多項式時間アルゴリズムが存在
する。
充足可能性問題
(Satisfiability Problem)
• このことは、充足可能性問題が、NPの中で、ある意
味「最も難しい」問題であることを意味している。
クラスNP
充足可能性問題
問題
問題
問題
問題
NP完全問題
(NP-Complete Problems)
• 最後に、Cook は充足可能性問題の他にも、「最も
難しい」という性質を持つ問題がNPの中にあること
を予想した。
• この予想は事実であり、1972年、 Rechard Karp
は、巡回セールスマン問題を含む、多くの組み合わ
せ問題の判定問題版が、充足可能性問題と「同じ
難しさ」であることを証明した。
• その後も、多くの問題がこれらの問題と「同じ難しさ」
であることが証明され、このような問題で構成される
クラスは「NP完全問題のクラス」と名付けられた。
NP完全問題
(NP-Complete Problems)
クラスNP
問題
NP完全問題のクラス 問題
問題
充足可能性問題
問題
問題
問題
問題
問題
NP完全問題
(NP-Complete Problems)
判定問題
クラスNP
NP完全問題のクラス
“undecidable”な問題
“nondeterministically”な問題
“intractable”
NP完全問題
(NP-Complete Problems)
• 一つの単純な疑問:
NP完全問題は“intractable”か?
• この問題は未解決である。
• 多くの研究者はNP完全問題が“intractable”であ
るという予想に同意している。
• 問題がNP完全であることは、少なくとも、それを解く
多項式時間アルゴリズムを見つけるためには、重大
な大発見が必要であることを示唆している。
NP完全問題(まとめ)
• 問題の間の相関関係
– 帰着
• NP完全性の理論(Cook の論文)
– 多項式時間帰着可能性
– クラスNP
– 充足可能性問題
– NP完全問題
目次 (Chapter 1)
1. イントロダクション
2. 問題,アルゴリズム,複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. NP完全問題
6. この本の概略
この本の概略
• この本は、問題がNP完全であるかどうかを決定す
る方法における入門書である。
• さらに、NP完全であることが知られた問題を扱う際
に利用できる、いくつかの方法についても議論する。
この本の概略
Chapter 2: The Theory of NP-Completeness


NP完全性の正式な定義
Cook の定理の証明
Chapter 3: Proving NP-Completeness Results

問題がNP完全であることの証明法
(既知のNP完全問題からの多項式帰着)
Chapter 4: Using NP-Completeness to Analyze
Problems

NP完全性を用いた問題の複雑さの解析
Chapter 5: NP-Hardness

判定問題から一般の問題への拡張
この本の概略
Chapter 6: Coping with NP-Complete Problems

近似アルゴリズムに関する話題
Chapter 7: Beyond NP-Completeness

計算の複雑さに関する話題
Appendix: A List of NP-Completeness Problems


NP完全であることが知られている問題のリスト
Open Problem
ダウンロード

PPTファイル 193KB