スライド 1 - System Architecture and Design Laboratory

目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
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”な計算機モデルではないが、ＮＰ完全
性の理論において重要な役割を担っている。
（Chapter 2 で詳しく説明）
証明可能な“intractable”な問題
（まとめ）
• 現在知られている“intractable”な問題は、
– “undecidable”な問題
– “nondeterministically”な問題
のどちらかである。
• もし、このどちらかであることを示すことができれば、
問題が“intractable”であることを証明できる。
• しかしながら、実際に遭遇する、一見“intractable”
に見える問題の多くは、上のどちらにも属さない。
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
ＮＰ完全問題
• 問題の間の相関関係
• ＮＰ完全性の理論（Cook の論文）
ＮＰ完全問題
• 問題の間の相関関係
– 帰着 (reducing)
• ＮＰ完全性の理論（Cook の論文）
問題の間の相関関係
• 問題と問題の間にある関係は、アルゴリズムデザイ
ナーに有用な情報を提供する。
• 二つの問題の間に関係があることを示すときに、
「帰着」という概念がよく使われる。
• 問題 A を問題 B へ帰着 (reducing) するとは：
– A の任意のインスタンスから等価な B のインス
タンスへの構成的な変換（写像）を与えること。
– このような変換は、 B を解くアルゴリズムを A を
解くアルゴリズムに変換する方法を与える。
帰着 (reducing)
問題 A
問題 B
インスタンス
の集合
インスタンス
の集合
？
アルゴリズム
アルゴリズム
解
解
帰着 (reducing)
問題 A
問題 B
問題 B が解ければ、
問題 A も解ける。
これらの問題のうち、１つで
も解ければ、他のすべての問題１
問題も解ける。
問題２
問題３
⇒同じ難しさの問題
問題５
問題４
ＮＰ完全問題
• 問題の間の相関関係
• ＮＰ完全性の理論（Cook の論文）
– 多項式時間帰着可能性
– クラスＮＰ
– 充足可能性問題
– ＮＰ完全問題
ＮＰ完全性の理論
• ＮＰ完全性の理論の基盤は、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
多項式時間
アルゴリズム
インスタンス
の集合
多項式時間
アルゴリズム
解
多項式時間
アルゴリズム
解
クラスＮＰ (Class NP)
• 次に Cook が注目したのは、クラスＮＰであった。
• クラスＮＰ：
– “nondeterministic”コンピュータ上で、多項式時
間で解くことのできる判定問題のクラス
– 判定問題：解が“yes”か“no”である問題
• 実際に遭遇する“intractable”に見える問題は、判
定問題に言い換えたとき、このクラスに属する。
クラスＮＰ (Class NP)
判定問題
クラスＮＰ
“undecidable”な問題
“nondeterministically”な問題
“intractable”
充足可能性問題
(Satisfiability Problem)
• 充足可能性問題は、クラスＮＰに属する問題の一つ
である。
• Cook は、次のことを証明した：
– クラスＮＰに属するすべての問題は、充足可能性
問題に多項式時間帰着可能である。
– すなわち、充足可能性問題を解く多項式時間ア
ルゴリズムが存在するならば、ＮＰに属するすべ
ての問題には、多項式時間アルゴリズムが存在
する。
充足可能性問題
(Satisfiability Problem)
• このことは、充足可能性問題が、ＮＰの中で、ある意
味「最も難しい」問題であることを意味している。
クラスＮＰ
充足可能性問題
問題
問題
問題
問題
ＮＰ完全問題
(NP-Complete Problems)
• 最後に、Cook は充足可能性問題の他にも、「最も
難しい」という性質を持つ問題がＮＰの中にあること
を予想した。
• この予想は事実であり、1972年、 Rechard Karp
は、巡回セールスマン問題を含む、多くの組み合わ
せ問題の判定問題版が、充足可能性問題と「同じ
難しさ」であることを証明した。
• その後も、多くの問題がこれらの問題と「同じ難しさ」
であることが証明され、このような問題で構成される
クラスは「ＮＰ完全問題のクラス」と名付けられた。
ＮＰ完全問題
(NP-Complete Problems)
クラスＮＰ
問題
ＮＰ完全問題のクラス問題
問題
充足可能性問題
問題
問題
問題
問題
問題
ＮＰ完全問題
(NP-Complete Problems)
判定問題
クラスＮＰ
ＮＰ完全問題のクラス
“undecidable”な問題
“nondeterministically”な問題
“intractable”
ＮＰ完全問題
(NP-Complete Problems)
• 一つの単純な疑問：
ＮＰ完全問題は“intractable”か？
• この問題は未解決である。
• 多くの研究者はＮＰ完全問題が“intractable”であ
るという予想に同意している。
• 問題がＮＰ完全であることは、少なくとも、それを解く
多項式時間アルゴリズムを見つけるためには、重大
な大発見が必要であることを示唆している。
ＮＰ完全問題（まとめ）
• 問題の間の相関関係
– 帰着
• ＮＰ完全性の理論（Cook の論文）
– 多項式時間帰着可能性
– クラスＮＰ
– 充足可能性問題
– ＮＰ完全問題
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
この本の概略
• この本は、問題がＮＰ完全であるかどうかを決定す
る方法における入門書である。
• さらに、ＮＰ完全であることが知られた問題を扱う際
に利用できる、いくつかの方法についても議論する。
この本の概略
Chapter 2: The Theory of NP-Completeness


ＮＰ完全性の正式な定義
Cook の定理の証明
Chapter 3: Proving NP-Completeness Results

問題がＮＰ完全であることの証明法
（既知のＮＰ完全問題からの多項式帰着）
Chapter 4: Using NP-Completeness to Analyze
Problems

ＮＰ完全性を用いた問題の複雑さの解析
Chapter 5: NP-Hardness

判定問題から一般の問題への拡張
この本の概略
Chapter 6: Coping with NP-Complete Problems

近似アルゴリズムに関する話題
Chapter 7: Beyond NP-Completeness

計算の複雑さに関する話題
Appendix: A List of NP-Completeness Problems


ＮＰ完全であることが知られている問題のリスト
Open Problem

Download Report