スライド 1

COMPUTERS AND INTRACTABILITY
A Guide to the Theory of NP-Completeness
Michael R. Garey / David S. Johnson
(c) 1979 Bell Telephone Laboratories, Incorporated
1
CONTENTS
Preface
1. Computers, Complexity, and Intractability
2. The Theory of NP-Completeness
3. Proving NP-Completeness Results
4. Using NP-Completeness to Analyze Problems
5. NP-Hardness
6. Coping with NP-Complete Problems
7. Beyond NP-Completeness
Appendix: A List of NP-Completeness Problems
2
CHAPTER 1
Computers, Complexity, and Intractability
3
CONTENTS (Chapter 1)
1. Introduction
2. Problems, Algorithms, and Complexity
3. Polynomial Time Algorithms and
Intractable Problems
4. Provably Intractable Problems
5. NP-Complete Problems
6. An Outline of the Book
4
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
5
イントロダクション
• この本の主題は、次のような多少風変わりな
例を通した紹介が良いかもしれない
6
• あなたは雇われの身のアルゴリズムデザイ
ナー
• 会社のために良いアルゴリズムを見つけるの
が仕事
• ある日、あなたは上司に呼び出されます・・・
7
上司の部屋で・・・
新しい市場に乗り出そうと思
うんだがね
上司
は、はあ・・・
あなた
8
上司の部屋で・・・
バンダースナッチを作ろうと
思うんだ
上司
バンダースナッチ？
あなた
9
バンダースナッチの作り方
構成要素１
・・・
構成要素２
・・・
構成要素３
・・・
・・・
10
バンダースナッチの作り方
構成要素１
・・・
構成要素２
・・・
構成要素３
・・・
構成要素N
・・・
要求：
コスト
重量
かっこよさ
etc.
・・・
・・・
11
バンダースナッチ問題
• 要求を満たしているかどうかを調
べる方法は？
• 要求を満たすような構成要素の
組を見つける方法は？
アルゴリズムを探せ！
12
上司の部屋で・・・
ということなんだがね
上司
は、はあ・・・
あなた
13
上司の部屋で・・・
やってくれるかね
上司
わかりました
お任せください
あなた
14
こうしてあなたは
バンダースナッチ問題を解くべく
必死に仕事に取り組みました
数週間後・・・
15
上司の部屋で・・・
どうだね、できたかね
上司
一応できたことはできたん
ですが・・・
あなた
16
上司の部屋で・・・
どれどれ
・・・・・・・・・
上司
ゴクリ
あなた
17
上司の部屋で・・・
なんだねこれは！
これじゃあ一つ設計するのに一
年もかかってしまう！
上司
すみません、
もうすこし時間をください
あなた
18
実はあなたは
考えうるすべての設計を調べるという以外に
実質的に優れたアルゴリズムを
提案できなかったのです
19
あなたはこれからどうすればよいのでしょうか？
この数週間で、あなたのやる気は
ほとんど失われてしまいました。
このまま続けても
おそらく同じでしょう。
20
しかし、あなたは上司の部屋に行って、
「私は頭が悪いので、能率的なアルゴリズムを
見つけられませんでした」
とは報告したくない。
これでは、
たとえクビになったとしても
文句は言えないでしょう。
21
もし、バンダースナッチ問題の
Inherent Intractability
（それを高速に解くことのできる
アルゴリズムが無いこと）
を証明することができれば、
会社でのあなたの地位に対する
深刻な被害を避けることができる
22
Inherent Intractability
• inherent 【形】 / inhi@[ｫ]r[ｫ]nt /
– ＜性質・属性・権利などが＞本来備わっている，
生れつき存在する；固有の，持ち前の
• intractable 【形】 / i$ntrQ@ktｫbl /
– ［けなして］手に負えない，扱いにくい，強情な，
– 処理［加工，治療］しにくい
– intractability 【名】
ジーニアス英和辞典より
23
Inherent Intractability
• これが証明できれば、上司の部屋に行き、
「私が能率的なアルゴリズムを発見できないのは、
そのようなアルゴリズムが存在しないからだ！」
と宣言できる。
24
Inherent Intractability
• しかしながら、問題の
Inherent Intractability
（能率的なアルゴリズムが無いこと）
を証明するのは能率的なアルゴリズムを見つ
けるのと同じくらい難しい
⇒ ＮＰ完全性の理論
25
Inherent Intractability と
ＮＰ完全性
• Inherent Intractability
– 問題に対する能率的なアルゴリズムが「絶対に無い」こと
• ＮＰ完全性
– 問題に対する能率的なアルゴリズムが
「おそらく無い」であろうということ。
– なぜなら、ＮＰ完全性を持つ問題は、これまでに様々な
専門家たちによって考えられてきたが、未だに誰一人
能率的なアルゴリズムを発見できていないからである。
26
ＮＰ完全性の理論
• もし、バンダースナッチ問題が、ＮＰ完全問題
と「ちょうど同じ難しさ」であることがわかった
らどうでしょうか？
• ＮＰ完全問題は、多くの有名な専門家たちが、
能率的なアルゴリズムを見つけることができ
なかった問題です。
• このとき、あなたは上司の部屋へ行き、
27
ＮＰ完全性の理論
「私は能率的なアルゴリズムを発見できな
かった。しかし、これらの有名な専門家たち
にも発見できていない！」と公表できる。
28
ＮＰ完全性の理論
• このことは、少なくとも、あなたをクビにして、他のア
ルゴリズムの専門家を雇うことは意味が無いことを
上司に知らせるでしょう。
• そして、あなたはバンダースナッチ問題に対する能
率的なアルゴリズムを探す責務から解放されるで
しょう。
• しかし、すべてが解決したわけではありません。
• バンダースナッチ問題は、実際に解かなければなら
ない問題なのです。
29
ＮＰ完全性の理論
• バンダースナッチ問題がＮＰ完全性を持つという結
果は、あなたに様々な情報を与えます。
• あなたがこれから何をすれば良いかの指針となりま
す。
• 例えば：
– 能率的ではないが、なるべく速く動くアルゴリズムを探す
– 最も良い解を出す保証は無いが、なるべく良い解を出す
能率的なアルゴリズムを探す
– インスタンスが特別な場合にのみ有効な能率的なアルゴ
リズムを探す
30
イントロダクション（まとめ）
• 「ＮＰ完全性」が指し示すことは、
「アルゴリズムを探すことを諦めよ」
ということではありません。
• 「ＮＰ完全性の理論」の最も重要な適用は、
「アルゴリズムデザイナーの努力を、有用なアル
ゴリズムを導くための見込みのあるアプローチへ
向けること」
である。
31
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
32
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題
(Problems)
– アルゴリズム (Algorithms)
– 複雑さ
(Complexity)
33
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題 (Problems)
• パラメータ (Parameter)
• インスタンス (Instance)
• 例：巡回セールスマン問題
– アルゴリズム (Algorithms)
– 複雑さ
(Complexity)
34
問題 (Problems)
• 答えることが可能な一般的な質問
• いくつかのパラメータ・変数を持ち、その値は特定さ
れない
• 問題は：
– すべてのパラメータの一般的な記述
– 解がどんな特性を満たすことを要求しているかの
陳述
を与えることで記述される。
• 問題のインスタンスはすべてのパラメータに対して
特定の値を決めることによって得られる。
35
例：巡回セールスマン問題
(Traveling Salesman Problem)
• パラメータ：
– 「都市」の有限集合 C={c1,c2,…,cm}
– 都市の各組 ci,cj∈C の間の「距離」 d(ci,cj)
• 解：
– 都市の列〈cπ(1),cπ(2),…,cπ(m)〉のうち、
(∑1≦i≦m-1 d(cπ(i),cπ(i+1)))+d(cπ(m),cπ(1))
が最小となるもの
36
例：巡回セールスマン問題
(Traveling Salesman Problem)
• 次のグラフは巡回セールスマン問題の一つ
のインスタンスである：
– C={c1,c2,c3,c4 }
– d(c1,c2)=10,
…,d(c3,c4 )=3
• 解：〈c1,c2,c4 ,c3〉
• 順回路の長さ：
10+9+3+5 = 27
c1
10
c2
6
5
9
9
c3
3
c4
37
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題
(Problems)
– アルゴリズム (Algorithms)
•
•
•
•
アルゴリズムの能率 (Efficiency)
所要時間 (Time Requirement)
インスタンスサイズと入力長
Encoding Scheme
– 複雑さ
(Complexity)
38
アルゴリズム (Algorithms)
• 問題を解くための手続き
• 具体的には、コンピュータプログラム
• アルゴリズムが問題を解くとは：
– 問題のどんなインスタンスにも適用できる。
– そのインスタンスに対して常に解を生成すること
が保証されている。
– 例えば、巡回セールスマン問題に対しては、常に
最小な長さを与える列を構成することが必要。
39
アルゴリズムの能率 (Efficiency)
• 広い意味では、アルゴリズムを実行するために必要
なすべての計算資源に関係する
– ハードウェア量，時間
• ここでは、「時間」だけを考える
• アルゴリズムの所要時間 (Time Requirement)：
– 解を求めるまでにどのくらいの時間が必要か。
– インスタンスの「サイズ」によって決まる。
– サイズ：例えば、巡回セールスマン問題では、一般的に
は都市の数のこと。
– インスタンスサイズが大きいほど、所要時間も大きくなる。
40
アルゴリズムの所要時間
(Time Requirement)
• 所要時間 ← インスタンスサイズ
• インスタンスサイズ
– 数学的に正確に論じるには、都市の数だけでは不十分
– 都市間の距離も入力情報の一部である
• 問題のインスタンス：
– 有限個のアルファベットから選ばれた記号の有限文字列
とみなす
– この文字列の長さを「入力長 (input length)」という
– 「入力長」をインスタンスサイズとして使う
41
インスタンスサイズと入力長
インスタンスの集合
グラフ
c1
10
6
5
c3
c2
9
9
3
c4
Encoding Scheme
アルファベット
{c,[,],/,0,1,2,3,4,5,6,7,8,9}
Encoding Scheme
c[1]c[2]c[3]c[4]//10/5/9//6/9//3
有限文字列
入力長 = 32
42
Encoding Scheme
• encode 【動】 / enko@ud /
– ＜通信文・データなどを＞符号化［コード化］す
る；符号化して発信する (⇔decode)
• scheme 【名】 / ski@ /
– 計画，案；（政府）公共計画，（会社の）事業計画
– 陰謀，たくらみ
– 大綱；図式；計画表
– 組織，機構（哲学）体系；配列；配色
ジーニアス英和辞典より
43
アルゴリズムの能率 (Efficiency)
• アルゴリズムの能率の良し悪し：
– 所要時間（問題を解くのに必要な時間）の大小
– インスタンスのサイズが大きいほど必然的に多く
の時間が必要
• インスタンスのサイズ：
– 入力長
– encoding scheme に依存
• 入力長と所要時間の関係は？
⇒ Time Complexity Function
44
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題
(Problems)
– アルゴリズム (Algorithms)
– 複雑さ (Complexity)
• Time Complexity Function （時間複雑さ関数）
45
複雑さ (Complexity)
• Time Complexity Function
– 与えられた入力長に対して、その入力長をサイズ
として持つインスタンスに対する解を求めるのに
必要な時間の最大値を返す関数
インスタンス
32
インスタンス
入力長
（整数）
54分
インスタンス
インスタンス
26
インスタンス
インスタンス
42分
512
16分
F(32) = 54分
46
Time Complexity Function
• Time Complexity Function を正確に定義
するためには、次のものを固定する必要があ
る：
– Encoding Scheme
• インスタンスから入力長を算出する
– コンピュータモデル（コンピュータ）
• アルゴリズムが解を求めるのに必要な時間を
算出する
47
問題，アルゴリズム，複雑さ（まとめ）
• 問題 (Problems)
– 例：巡回セールスマン問題
• アルゴリズム (Algorithms)
– アルゴリズムの能率：所要時間
– インスタンスのサイズ：入力長
• 複雑さ (Complexity)
– Time Complexity Function：
入力長に対する所要時間を表現
48
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
49
多項式時間アルゴリズムと
“intractable”な問題
• アルゴリズムの能率の境界線
• ‘‘intractable’’な問題
50
多項式時間アルゴリズムと
“intractable”な問題
• アルゴリズムの能率の境界線：
– 多項式時間アルゴリズム vs. 指数関数時間アル
ゴリズム
– オーダー記法
– 多項式の成長 vs. 指数関数の成長
– コンピュータの性能向上の効果
• ‘‘intractable’’な問題
51
アルゴリズムの能率の境界線
• アルゴリズムの能率は Time complexity function
で決まる。
• アルゴリズムが
「十分能率的である」か「まったく非能率的である」
かの区別をどこでつけるのか?
多項式時間アルゴリズム
vs.
指数関数時間アルゴリズム
52
オーダー記法 (Big-Oh Notation)
• 任意の関数 f(n), g(n) に対して、 f(n) = O(g(n))
であるとは、ある定数 c, n0 が存在して、任意の n
≧n0 に対して、
|f(n)| ≦ c・|g(n)|
が成り立つときをいう。
53
多項式時間アルゴリズム
(Polynomial Time Algorithms)
• アルゴリズムが多項式時間アルゴリズムであるとは、
その Time complexity function F(n) に対して、あ
る多項式関数 p(n) が存在して、
F(n) = O(p(n))
が成り立つときをいう。
• 多項式関数とは、
p(n) = ∑0≦i≦N ai ni （Nは自然数）
で表される関数である（ただし、 ai は実数）。
54
指数関数時間アルゴリズム
(Exponential Time Algorithms)
• アルゴリズムが多項式時間アルゴリズムでないとき、
指数関数時間アルゴリズムであるという。
• すなわち、アルゴリズムの Time complexity
function F(n) が、すべての多項式関数 p(n) に対し
て、
F(n) = O(p(n))
とならないときをいう。
55
多項式時間アルゴリズムと
指数関数時間アルゴリズム
• 多項式時間アルゴリズム：
– Time complexity function が多項式で抑えられる
• 指数関数時間アルゴリズム：
– Time complexity function が多項式で抑えられない
多項式時間指数関数時間
アルゴリズムアルゴリズム
アルゴリズム
56
多項式時間アルゴリズム
vs. 指数関数時間アルゴリズム
• 「多項式時間アルゴリズムと指数関数時間アルゴリ
ズム」という区別にはどういう意味があるのか？
• 代表的な多項式関数
n, n2, n3, n5
と指数関数
2n, 3n
を Time complexity function として持つアルゴリズ
ムに対して、インスタンスサイズを大きくしていったと
きの所要時間の成長を比較する。
57
多項式の成長 vs. 指数関数の成長
Time
comp.
func.
インスタンスサイズ
10
n1
.00001
秒
n2
20
.00002
秒
30
.00003
秒
40
50
60
.00004
秒
.00005
秒
.00006
秒
.0001 秒 .0004 秒 .0009 秒
.0016 秒
.0025 秒
.0036 秒
n3
.001 秒
.008 秒
.027 秒
.064 秒
.125 秒
.216 秒
n5
.1 秒
3.2 秒
24.3 秒
1.7 分
5.2 分
13.0 分
2n
.001 秒
1.0 秒
17.9 分
12.7 日
35.7 年
366 世紀
3n
.059 秒
58 分
6.5 年
3855
世紀
2×108
世紀
1.3×1013
世紀
58
多項式の成長 vs. 指数関数の成長
• 多項式の成長に比べ、指数関数の成長は著
しく速い。
• 指数関数時間アルゴリズムでは、サイズの大
きなインスタンスに対しては、現実的な時間で
解くことができない。
• 指数関数時間アルゴリズム
＝「非能率的なアルゴリズム」
59
コンピュータの性能向上の効果
• コンピュータの性能が上がれば、指数関数時間アル
ゴリズムでも、サイズの大きなインスタンスを現実的
な時間で解くことができるようになるのではないか？
• それぞれの Time complexity function を持つアル
ゴリズムによって、１時間で解ける最大のインスタン
スサイズを比較
– 現在の計算機
– 現在の計算機より100倍速い計算機
– 現在の計算機より1000倍速い計算機
60
１時間で解くことのできる
最大のインスタンスサイズ
Time comp. 現在の計算 100倍速い
func.
機
計算機
n1
N1
100 N1
1000倍速い
計算機
1000 N1
n2
N2
10 N2
31.6 N2
n3
N3
4.64 N3
10 N3
n5
N4
2.5 N4
3.98 N4
2n
N5
N5 + 6.64
N5 + 9.97
3n
N6
N6 + 4.19
N6 + 6.29
61
アルゴリズムの能率
• 能率的なアルゴリズム：
多項式時間アルゴリズム
• 非能率的なアルゴリズム：
指数関数時間アルゴリズム
• ただし、あるインスタンスサイズまでは、指数関数時
間アルゴリズムのほうが、多項式時間アルゴリズム
よりも速いという場合もある。
62
いくつかの注意点
• Time complexity function が n100 や 1099n2 のよう
なとき、そのアルゴリズムは能率的といえるのか？
• 実際に現れた問題を多項式時間で解くことができる
とき、その多項式は：
– 次数は 2 か 3
– 極端に大きな係数を持たない
という傾向にある。
63
いくつかの注意点
• 実際には有用な指数関数時間アルゴリズムも存在
する：
– 線形計画法の Simplex Algorithm
– ナップザック問題の Branch-and-Bound Algorithm
• これらのアルゴリズムは、「ワーストケース」のときに
のみ、計算に指数関数時間必要である。
（Time complexity function は、最大の所要時間で
定義された。）
• このような状況が起こるのは稀である。
64
多項式時間アルゴリズムと
“intractable”な問題
• アルゴリズムの能率の境界線
• ‘‘intractable’’な問題
– Encoding Scheme と計算機モデルの影響
– “reasonable”な Encoding Scheme
– “reasonable”な計算機モデル
65
“intractable”な問題
• 問題が“intractable”であるとは、その問題を解く多
項式時間アルゴリズムが存在しないときをいう。
• 多項式時間アルゴリズム：
– Time complexity function を多項式で抑えることができる
アルゴリズム
• Time complexity function は、
– Encoding Scheme
– 計算機モデル
に依存する。
66
Encoding Scheme と計算機モデル
の影響
• 問題が“intractable”であるかどうかは、 Encoding
Scheme と計算機モデルに依存するか？
• Encoding Scheme と計算機モデルを、それぞれ
– “reasonable”な Encoding Scheme
– “reasonable”な計算機モデル
に制限すれば、問題が“intractable”であるかどう
かに影響しない。
67
“reasonable”な Encoding Scheme
• 例として、インスタンスがグラフ：
G = (V,E)
のときを考える。
• 例：右図のグラフの場合
V1
V = {V1, V2, V3, V4}
E = {(V1,V2), (V2,V3)}
V2
V3
V4
68
“reasonable”な Encoding Scheme
• グラフの Encoding Scheme としては
– 頂点リストと辺リスト
– 隣接リスト
– 隣接行列の行のリスト
が一般的に使われる。
Encoding Scheme
頂点リストと辺リスト
V1
V3
V2
V4
文字列
長さ
36
隣接リスト
V[1]V[2]V[3]V[4]
(V[1]V[2])(V[2]V[3])
(V[2])(V[1]V[3])(V[2])()
隣接行列の行リスト
0100/1010/0010/0000
19 69
24
“reasonable”な Encoding Scheme
• グラフ G=(V,E) に対する、これらの Encoding
Scheme による入力長の上限と下限を示す。
（ただし、 v=|V|, e=|E| であり、 e＜v2 ）
• これらの Encoding Scheme による入力長は、高々
多項式的に違うだけである。
Encoding Scheme
下限
上限
頂点リストと辺リスト
4v+10e
隣接リスト
2v+8e
4v+10e+(v+2e)・
ceil(log10v)
2v+8e+2e・ceil(log10v)
隣接行列の行リスト
v2+v-1
v2+v-1
70
“reasonable”な Encoding Scheme
• “reasonable”の意味するもの：
– 各インスタンスの encoding は簡潔であり、必要
のない情報は詰め込まれていない。
– 各インスタンスに含まれる数字は二進（または十
進，八進など、１以外の固定進）で提示されてい
る。
• これらの条件を満たす Encoding Scheme に制限
すれば、与えられた問題が“intractable”かどうか
の決定には影響しないだろう。
71
“reasonable”な計算機モデル
• 計算機モデルに対しても、同様なことが言える。
• マシンＢにおいて Time Complexity T(n) を持つアル
ゴリズムの、マシンＡでの Time Complexity を示す。
Simulated
machine B
1-Tape Turing
Machine (1TM)
k-Tape Turing
Machine (kTM)
Random Access
Machine (RAM)
Simulating machine A
1TM
kTM
RAM
O(T(n)) O(T(n)logT(n))
－
O(T2(n))
－
O(T3(n)) O(T2(n))
O(T(n)logT(n))
－
72
“reasonable”な計算機モデル
• これらの計算機モデル上では、アルゴリズムの複雑
度は、多項式的かどうかの観点から見れば同じで
ある。
• ここでの“reasonable”の意味するものは、
「単一時間内にこなせる仕事の総量に、多項式の
限界があること」
である。
• 例えば、勝手に並列処理を行う能力を持つような計
算機モデルは“reasonable”ではない。
73
Encoding Scheme と計算機モデル
の影響
• “reasonable”な Encoding Scheme ：
– なるべく短い長さの文字列を出力する。
– 出力する文字列の長さは、多項式的以上には異ならない。
• “reasonable”な計算機モデル：
– 現実のコンピュータに近い。
– 多項式的かどうかの観点から見れば、アルゴリズムの複
雑さは異ならない。
• Encoding Scheme と計算機モデルに対して、この
ような制限をおけば、問題が“intractable”であるか
どうかに影響しない。
74
多項式時間アルゴリズムと
“intractable”な問題（まとめ）
• アルゴリズムの能率：
– 多項式時間アルゴリズム＝能率的
– 指数関数時間アルゴリズム＝非能率的
• “intractable”な問題
– 問題を解く多項式時間アルゴリズムが無いこと。
– Encoding Scheme 及び計算機モデルについて
は、“reasonable”なものに制限することで、問題
が“intractable”かどうかへの影響を取り除くこと
ができる。
75
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
76
証明可能な“intractable”な問題
• ‘‘intractable’’な問題の存在
– “undecidable”な問題
– “nondeterministically”な問題
77
“intractable”な問題の存在
• “intractable”な問題（多項式時間アルゴリズム
では解けない問題）は実際に存在するか？
• 問題が“intractable”となる要因：
– 問題が難しすぎて、解を求めるのに指数関数時
間必要である。
– 解自身が大きすぎて、入力長の多項式関数で抑
えられた長さの表現では記述できない。
78
“intractable”な問題の存在
• 解が大きすぎる問題：
例：巡回セールスマン問題の変形
• インスタンスに追加パラメータ B を持たせる。
• 「長さが B 以下のすべての巡回路を求めよ」
• この問題に対して、指数的に多くの巡回路が B 以下
の長さを持つように、インスタンスを構成可能。
• すなわち、解を全て書き出すことのできる多項式時間
アルゴリズムは存在しない。⇒“intractable”
しかし、このような問題は非現実的である。
• 我々が関心を向けるのは、一つめの要因に
絞られる。
79
“undecidable”な問題
• “undecidable”な問題：
– その問題を解くアルゴリズムが存在しない問題
• 1936年，アラン・チューリング
– 「任意のコンピュータプログラムと、そのプログラ
ムへの任意の入力が与えられたとき、そのプログ
ラムが有限時間内で停止するか否かを判定せ
よ」
– この問題を解くことのできるアルゴリズムは存在
しないことを示した。
80
“undecidable”な問題
• 現在、様々な“undecidable”な問題が知られてい
る：
– 有限表現群に関する自明な問題 [Rabin,1958]
– ヒルベルトの第十問題（整数上の多項式の解決可能性）
[Matijasevic,1970]
– “Tiling the plane”の問題 [Berger,1966]
• これらの問題は、どんなアルゴリズムでも（ましてや
多項式時間アルゴリズムなんかでは到底！）解けな
いので、強い意味で“intractable”である。
81
“nondeterministically”な問題
• “decidable”な（すなわち、“undecidable”でない）問題
の中に、“intractable”な問題を最初に見つけたの
は、Hartmains と Stearns [1965] であった。
• しかし、彼らの結果は、非常に特別な性質を持つ、
「人工的な」問題に限られていた。
• これに対して、「自然な」“decidable”問題のうちで
“intractable”な問題は、 Meyer と Stockmeyer
[1972]，Fischer とRabin [1974]によって与えられた。
• これらの問題は、現在“nondeterministically”な問
題として類別されている。
82
“nondeterministically”な問題
• “nondeterministically”な問題：
– “nondeterministic”コンピュータモデルでは、多項式時
間では解けない問題
• “nondeterministic”コンピュータモデル：
– 無限個の独立な計算を、並列に追跡する能力を持つ計算
機モデル
• 注： “nondeterministic”コンピュータモデルは、
“reasonable”な計算機モデルではないが、ＮＰ完全
性の理論において重要な役割を担っている。
（Chapter 2 で詳しく説明）
83
証明可能な“intractable”な問題
（まとめ）
• 現在知られている“intractable”な問題は、
– “undecidable”な問題
– “nondeterministically”な問題
のどちらかである。
• もし、このどちらかであることを示すことができれば、
問題が“intractable”であることを証明できる。
• しかしながら、実際に遭遇する、一見“intractable”
に見える問題の多くは、上のどちらにも属さない。
84
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
85
ＮＰ完全問題
• 問題の間の相関関係
• ＮＰ完全性の理論（Cook の論文）
86
ＮＰ完全問題
• 問題の間の相関関係
– 帰着 (reducing)
• ＮＰ完全性の理論（Cook の論文）
87
問題の間の相関関係
• 問題と問題の間にある関係は、アルゴリズムデザイ
ナーに有用な情報を提供する。
• 二つの問題の間に関係があることを示すときに、
「帰着」という概念がよく使われる。
• 問題 A を問題 B へ帰着 (reducing) するとは：
– A の任意のインスタンスから等価な B のインス
タンスへの構成的な変換（写像）を与えること。
– このような変換は、 B を解くアルゴリズムを A を
解くアルゴリズムに変換する方法を与える。
88
帰着 (reducing)
問題 A
問題 B
インスタンス
の集合
インスタンス
の集合
？
アルゴリズム
アルゴリズム
解
解
89
帰着 (reducing)
問題 A
問題 B
問題 B が解ければ、
問題 A も解ける。
これらの問題のうち、１つで
も解ければ、他のすべての問題１
問題も解ける。
問題２
問題３
⇒同じ難しさの問題
問題５
問題４
90
ＮＰ完全問題
• 問題の間の相関関係
• ＮＰ完全性の理論（Cook の論文）
– 多項式時間帰着可能性
– クラスＮＰ
– 充足可能性問題
– ＮＰ完全問題
91
ＮＰ完全性の理論
• ＮＰ完全性の理論の基盤は、1971年に提出された
Stephen Cook の論文：
“The Complexity of Theorem Proving Procedures”
に用意されていた。
• Cook は、まず多項式時間帰着可能性に注目した。
• 多項式時間帰着可能：
– 帰着に要求される変換が、多項式時間アルゴリ
ズムによって実行できること
92
多項式時間帰着可能性
(Polynomial Time Reducibility)
問題 A
インスタンス
の集合
多項式時間
アルゴリズム
変換
多項式時間
アルゴリズム
変換
解
問題 B
インスタンス
の集合
アルゴリズム
解
93
多項式時間帰着可能性
(Polynomial Time Reducibility)
• 問題 A が問題 B へ多項式時間帰着可能であり、
問題 B に対する多項式時間アルゴリズムが存在す
るとき、問題 A を解く多項式時間アルゴリズムの存
在がいえる。
94
多項式時間帰着可能性
(Polynomial Time Reducibility)
問題 A
インスタンス
の集合
問題 B
多項式時間
アルゴリズム
インスタンス
の集合
多項式時間
アルゴリズム
解
多項式時間
アルゴリズム
解
95
クラスＮＰ (Class NP)
• 次に Cook が注目したのは、クラスＮＰであった。
• クラスＮＰ：
– “nondeterministic”コンピュータ上で、多項式時
間で解くことのできる判定問題のクラス
– 判定問題：解が“yes”か“no”である問題
• 実際に遭遇する“intractable”に見える問題は、判
定問題に言い換えたとき、このクラスに属する。
96
クラスＮＰ (Class NP)
判定問題
クラスＮＰ
“undecidable”な問題
“nondeterministically”な問題
“intractable”
97
充足可能性問題
(Satisfiability Problem)
• 充足可能性問題は、クラスＮＰに属する問題の一つ
である。
• Cook は、次のことを証明した：
– クラスＮＰに属するすべての問題は、充足可能性
問題に多項式時間帰着可能である。
– すなわち、充足可能性問題を解く多項式時間ア
ルゴリズムが存在するならば、ＮＰに属するすべ
ての問題には、多項式時間アルゴリズムが存在
する。
98
充足可能性問題
(Satisfiability Problem)
• このことは、充足可能性問題が、ＮＰの中で、ある意
味「最も難しい」問題であることを意味している。
クラスＮＰ
充足可能性問題
問題
問題
問題
問題
99
ＮＰ完全問題
(NP-Complete Problems)
• 最後に、Cook は充足可能性問題の他にも、「最も
難しい」という性質を持つ問題がＮＰの中にあること
を予想した。
• この予想は事実であり、1972年、 Rechard Karp
は、巡回セールスマン問題を含む、多くの組み合わ
せ問題の判定問題版が、充足可能性問題と「同じ
難しさ」であることを証明した。
• その後も、多くの問題がこれらの問題と「同じ難しさ」
であることが証明され、このような問題で構成される
クラスは「ＮＰ完全問題のクラス」と名付けられた。
100
ＮＰ完全問題
(NP-Complete Problems)
クラスＮＰ
問題
ＮＰ完全問題のクラス問題
問題
充足可能性問題
問題
問題
問題
問題
問題
101
ＮＰ完全問題
(NP-Complete Problems)
判定問題
クラスＮＰ
ＮＰ完全問題のクラス
“undecidable”な問題
“nondeterministically”な問題
“intractable”
102
ＮＰ完全問題
(NP-Complete Problems)
• 一つの単純な疑問：
ＮＰ完全問題は“intractable”か？
• この問題は未解決である。
• 多くの研究者はＮＰ完全問題が“intractable”であ
るという予想に同意している。
• 問題がＮＰ完全であることは、少なくとも、それを解く
多項式時間アルゴリズムを見つけるためには、重大
な大発見が必要であることを示唆している。
103
ＮＰ完全問題（まとめ）
• 問題の間の相関関係
– 帰着
• ＮＰ完全性の理論（Cook の論文）
– 多項式時間帰着可能性
– クラスＮＰ
– 充足可能性問題
– ＮＰ完全問題
104
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
105
この本の概略
• この本は、問題がＮＰ完全であるかどうかを決定す
る方法における入門書である。
• さらに、ＮＰ完全であることが知られた問題を扱う際
に利用できる、いくつかの方法についても議論する。
106
この本の概略
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

判定問題から一般の問題への拡張
107
この本の概略
Chapter 6: Coping with NP-Complete Problems

近似アルゴリズムに関する話題
Chapter 7: Beyond NP-Completeness

計算の複雑さに関する話題
Appendix: A List of NP-Completeness Problems


ＮＰ完全であることが知られている問題のリスト
Open Problem
108

Download Report