COMPUTERS AND INTRACTABILITY
A Guide to the Theory of NP-Completeness
Michael R. Garey / David S. Johnson
(c) 1979 Bell Telephone Laboratories, Incorporated
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
CHAPTER 1
Computers, Complexity, and Intractability
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
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
イントロダクション
• この本の主題は、次のような多少風変わりな
例を通した紹介が良いかもしれない
• あなたは雇われの身のアルゴリズムデザイ
ナー
• 会社のために良いアルゴリズムを見つけるの
が仕事
• ある日、あなたは上司に呼び出されます・・・
上司の部屋で・・・
新しい市場に乗り出そうと思
うんだがね
上司
は、はあ・・・
あなた
上司の部屋で・・・
バンダースナッチを作ろうと
思うんだ
上司
バンダースナッチ？
あなた
バンダースナッチの作り方
構成要素１
・・・
構成要素２
・・・
構成要素３
・・・
・・・
バンダースナッチの作り方
構成要素１
・・・
構成要素２
・・・
構成要素３
・・・
構成要素N
・・・
・・・
・・・
要求：
コスト
重量
かっこよさ
etc.
バンダースナッチ問題
• 要求を満たしているかどうかを調
べる方法は？
• 要求を満たすような構成要素の
組を見つける方法は？
アルゴリズムを探せ！
上司の部屋で・・・
ということなんだがね
上司
は、はあ・・・
あなた
上司の部屋で・・・
やってくれるかね
上司
わかりました
お任せください
あなた
こうしてあなたは
バンダースナッチ問題を解くべく
必死に仕事に取り組みました
数週間後・・・
上司の部屋で・・・
どうだね、できたかね
上司
一応できたことはできたん
ですが・・・
あなた
上司の部屋で・・・
どれどれ
・・・・・・・・・
上司
ゴクリ
あなた
上司の部屋で・・・
なんだね これは！
これじゃあ一つ設計するのに一
年もかかってしまう！
上司
すみません、
もうすこし時間をください
あなた
実はあなたは
考えうるすべての設計を調べるという以外に
実質的に優れたアルゴリズムを
提案できなかったのです
あなたはこれからどうすればよいのでしょうか？
この数週間で、あなたのやる気は
ほとんど失われてしまいました。
このまま続けても
おそらく同じでしょう。
しかし、あなたは上司の部屋に行って、
「私は頭が悪いので、能率的なアルゴリズムを
見つけられませんでした」
とは報告したくない。
これでは、
たとえクビになったとしても
文句は言えないでしょう。
もし、バンダースナッチ問題の
Inherent Intractability
（それを高速に解くことのできる
アルゴリズムが無いこと）
を証明することができれば、
会社でのあなたの地位に対する
深刻な被害を避けることができる
Inherent Intractability
• inherent 【形】 / inhi@[ｫ]r[ｫ]nt /
– ＜性質・属性・権利などが＞本来備わっている，
生れつき存在する； 固有の，持ち前の
• intractable 【形】 / i$ntrQ@ktｫbl /
– ［けなして］ 手に負えない，扱いにくい，強情な，
– 処理［加工，治療］しにくい
– intractability 【名】
ジーニアス英和辞典より
Inherent Intractability
• これが証明できれば、上司の部屋に行き、
「私が能率的なアルゴリズムを発見できないのは、
そのようなアルゴリズムが存在しないからだ！」
と宣言できる。
Inherent Intractability
• しかしながら、問題の
Inherent Intractability
（能率的なアルゴリズムが無いこと）
を証明するのは能率的なアルゴリズムを見つ
けるのと同じくらい難しい
⇒ ＮＰ完全性の理論
Inherent Intractability と
ＮＰ完全性
• Inherent Intractability
– 問題に対する能率的なアルゴリズムが「絶対に無い」こと
• ＮＰ完全性
– 問題に対する能率的なアルゴリズムが
「おそらく無い」であろうということ。
– なぜなら、ＮＰ完全性を持つ問題は、これまでに様々な
専門家たちによって考えられてきたが、未だに誰一人
能率的なアルゴリズムを発見できていないからである。
ＮＰ完全性の理論
• もし、バンダースナッチ問題が、ＮＰ完全問題
と「ちょうど同じ難しさ」であることがわかった
らどうでしょうか？
• ＮＰ完全問題は、多くの有名な専門家たちが、
能率的なアルゴリズムを見つけることができ
なかった問題です。
• このとき、あなたは上司の部屋へ行き、
ＮＰ完全性の理論
「私は能率的なアルゴリズムを発見できな
かった。 しかし、これらの有名な専門家たち
にも発見できていない！」 と公表できる。
ＮＰ完全性の理論
• このことは、少なくとも、あなたをクビにして、他のア
ルゴリズムの専門家を雇うことは意味が無いことを
上司に知らせるでしょう。
• そして、あなたはバンダースナッチ問題に対する能
率的なアルゴリズムを探す責務から解放されるで
しょう。
• しかし、すべてが解決したわけではありません。
• バンダースナッチ問題は、実際に解かなければなら
ない問題なのです。
ＮＰ完全性の理論
• バンダースナッチ問題がＮＰ完全性を持つという結
果は、あなたに様々な情報を与えます。
• あなたがこれから何をすれば良いかの指針となりま
す。
• 例えば：
– 能率的ではないが、なるべく速く動くアルゴリズムを探す
– 最も良い解を出す保証は無いが、なるべく良い解を出す
能率的なアルゴリズムを探す
– インスタンスが特別な場合にのみ有効な能率的なアルゴ
リズムを探す
イントロダクション（まとめ）
• 「ＮＰ完全性」が指し示すことは、
「アルゴリズムを探すことを諦めよ」
ということではありません。
• 「ＮＰ完全性の理論」の最も重要な適用は、
「アルゴリズムデザイナーの努力を、有用なアル
ゴリズムを導くための見込みのあるアプローチへ
向けること」
である。
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題
(Problems)
– アルゴリズム (Algorithms)
– 複雑さ
(Complexity)
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題 (Problems)
• パラメータ (Parameter)
• インスタンス (Instance)
• 例：巡回セールスマン問題
– アルゴリズム (Algorithms)
– 複雑さ
(Complexity)
問題 (Problems)
• 答えることが可能な一般的な質問
• いくつかのパラメータ・変数を持ち、その値は特定さ
れない
• 問題は：
– すべてのパラメータの一般的な記述
– 解がどんな特性を満たすことを要求しているかの
陳述
を与えることで記述される。
• 問題のインスタンスはすべてのパラメータに対して
特定の値を決めることによって得られる。
例：巡回セールスマン問題
(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))
が最小となるもの
例：巡回セールスマン問題
(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
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題
(Problems)
– アルゴリズム (Algorithms)
•
•
•
•
アルゴリズムの能率 (Efficiency)
所要時間 (Time Requirement)
インスタンスサイズと入力長
Encoding Scheme
– 複雑さ
(Complexity)
アルゴリズム (Algorithms)
• 問題を解くための手続き
• 具体的には、コンピュータプログラム
• アルゴリズムが問題を解くとは：
– 問題のどんなインスタンスにも適用できる。
– そのインスタンスに対して常に解を生成すること
が保証されている。
– 例えば、巡回セールスマン問題に対しては、常に
最小な長さを与える列を構成することが必要。
アルゴリズムの能率 (Efficiency)
• 広い意味では、アルゴリズムを実行するために必要
なすべての計算資源に関係する
– ハードウェア量，時間
• ここでは、「時間」だけを考える
• アルゴリズムの所要時間 (Time Requirement)：
– 解を求めるまでにどのくらいの時間が必要か。
– インスタンスの「サイズ」によって決まる。
– サイズ： 例えば、巡回セールスマン問題では、一般的に
は都市の数のこと。
– インスタンスサイズが大きいほど、所要時間も大きくなる。
アルゴリズムの所要時間
(Time Requirement)
• 所要時間 ← インスタンスサイズ
• インスタンスサイズ
– 数学的に正確に論じるには、都市の数だけでは不十分
– 都市間の距離も入力情報の一部である
• 問題のインスタンス：
– 有限個のアルファベットから選ばれた記号の有限文字列
とみなす
– この文字列の長さを「入力長 (input length)」という
– 「入力長」をインスタンスサイズとして使う
インスタンスサイズと入力長
インスタンスの集合
グラフ
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
Encoding Scheme
• encode 【動】 / enko@ud /
– ＜通信文・データなどを＞符号化［コード化］す
る；符号化して発信する (⇔decode)
• scheme 【名】 / ski@ /
– 計画，案；（政府）公共計画，（会社の）事業計画
– 陰謀，たくらみ
– 大綱；図式；計画表
– 組織，機構（哲学）体系；配列；配色
ジーニアス英和辞典より
アルゴリズムの能率 (Efficiency)
• アルゴリズムの能率の良し悪し：
– 所要時間（問題を解くのに必要な時間）の大小
– インスタンスのサイズが大きいほど必然的に多く
の時間が必要
• インスタンスのサイズ：
– 入力長
– encoding scheme に依存
• 入力長と所要時間の関係は？
⇒ Time Complexity Function
問題，アルゴリズム，複雑さ
• これからの議論を正確にするため、基本的な
言葉の意味を取り決めておく必要がある：
– 問題
(Problems)
– アルゴリズム (Algorithms)
– 複雑さ (Complexity)
• Time Complexity Function （時間複雑さ関数）
複雑さ (Complexity)
• Time Complexity Function
– 与えられた入力長に対して、その入力長をサイズ
として持つインスタンスに対する解を求めるのに
必要な時間の最大値を返す関数
インスタンス
32
インスタンス
入力長
（整数）
54分
インスタンス
インスタンス
26
インスタンス
インスタンス
42分
512
16分
F(32) = 54分
Time Complexity Function
• Time Complexity Function を正確に定義
するためには、次のものを固定する必要があ
る：
– Encoding Scheme
• インスタンスから入力長を算出する
– コンピュータモデル（コンピュータ）
• アルゴリズムが解を求めるのに必要な時間を
算出する
問題，アルゴリズム，複雑さ（まとめ）
• 問題 (Problems)
– 例： 巡回セールスマン問題
• アルゴリズム (Algorithms)
– アルゴリズムの能率： 所要時間
– インスタンスのサイズ： 入力長
• 複雑さ (Complexity)
– Time Complexity Function：
入力長に対する所要時間を表現
目次 (Chapter 1)
1. イントロダクション
2. 問題，アルゴリズム，複雑さ
3. 多項式時間アルゴリズムと ‘‘intractable’’
な問題
4. 証明可能な ‘‘intractable’’な問題
5. ＮＰ完全問題
6. この本の概略
多項式時間アルゴリズムと
“intractable”な問題
• アルゴリズムの能率の境界線
• ‘‘intractable’’な問題
多項式時間アルゴリズムと
“intractable”な問題
• アルゴリズムの能率の境界線：
– 多項式時間アルゴリズム vs. 指数関数時間アル
ゴリズム
– オーダー記法
– 多項式の成長 vs. 指数関数の成長
– コンピュータの性能向上の効果
• ‘‘intractable’’な問題
アルゴリズムの能率の境界線
• アルゴリズムの能率は Time complexity function
で決まる。
• アルゴリズムが
「十分能率的である」か「まったく非能率的である」
かの区別をどこでつけるのか?
多項式時間アルゴリズム
vs.
指数関数時間アルゴリズム
オーダー記法 (Big-Oh Notation)
• 任意の関数 f(n), g(n) に対して、 f(n) = O(g(n))
であるとは、ある定数 c, n0 が存在して、任意の n
≧n0 に対して、
|f(n)| ≦ c・|g(n)|
が成り立つときをいう。
多項式時間アルゴリズム
(Polynomial Time Algorithms)
• アルゴリズムが多項式時間アルゴリズムであるとは、
その Time complexity function F(n) に対して、あ
る多項式関数 p(n) が存在して、
F(n) = O(p(n))
が成り立つときをいう。
• 多項式関数とは、
p(n) = ∑0≦i≦N ai ni （Nは自然数）
で表される関数である（ただし、 ai は実数）。
指数関数時間アルゴリズム
(Exponential Time Algorithms)
• アルゴリズムが多項式時間アルゴリズムでないとき、
指数関数時間アルゴリズムであるという。
• すなわち、アルゴリズムの Time complexity
function F(n) が、すべての多項式関数 p(n) に対し
て、
F(n) = O(p(n))
とならないときをいう。
多項式時間アルゴリズムと
指数関数時間アルゴリズム
• 多項式時間アルゴリズム：
– Time complexity function が多項式で抑えられる
• 指数関数時間アルゴリズム：
– Time complexity function が多項式で抑えられない
多項式時間 指数関数時間
アルゴリズム アルゴリズム
アルゴリズム
多項式時間アルゴリズム
vs. 指数関数時間アルゴリズム
• 「多項式時間アルゴリズムと指数関数時間アルゴリ
ズム」という区別にはどういう意味があるのか？
• 代表的な多項式関数
n, n2, n3, n5
と指数関数
2n, 3n
を Time complexity function として持つアルゴリズ
ムに対して、インスタンスサイズを大きくしていったと
きの所要時間の成長を比較する。
多項式の成長 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
世紀
多項式の成長 vs. 指数関数の成長
• 多項式の成長に比べ、指数関数の成長は著
しく速い。
• 指数関数時間アルゴリズムでは、サイズの大
きなインスタンスに対しては、現実的な時間で
解くことができない。
• 指数関数時間アルゴリズム
＝ 「非能率的なアルゴリズム」
コンピュータの性能向上の効果
• コンピュータの性能が上がれば、指数関数時間アル
ゴリズムでも、サイズの大きなインスタンスを現実的
な時間で解くことができるようになるのではないか？
• それぞれの Time complexity function を持つアル
ゴリズムによって、１時間で解ける最大のインスタン
スサイズを比較
– 現在の計算機
– 現在の計算機より100倍速い計算機
– 現在の計算機より1000倍速い計算機
１時間で解くことのできる
最大のインスタンスサイズ
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
アルゴリズムの能率
• 能率的なアルゴリズム：
多項式時間アルゴリズム
• 非能率的なアルゴリズム：
指数関数時間アルゴリズム
• ただし、あるインスタンスサイズまでは、指数関数時
間アルゴリズムのほうが、多項式時間アルゴリズム
よりも速いという場合もある。
いくつかの注意点
• Time complexity function が n100 や 1099n2 のよう
なとき、そのアルゴリズムは能率的といえるのか？
• 実際に現れた問題を多項式時間で解くことができる
とき、その多項式は：
– 次数は 2 か 3
– 極端に大きな係数を持たない
という傾向にある。
いくつかの注意点
• 実際には有用な指数関数時間アルゴリズムも存在
する：
– 線形計画法の Simplex Algorithm
– ナップザック問題の Branch-and-Bound Algorithm
• これらのアルゴリズムは、「ワーストケース」のときに
のみ、計算に指数関数時間必要である。
（Time complexity function は、最大の所要時間で
定義された。）
• このような状況が起こるのは稀である。
多項式時間アルゴリズムと
“intractable”な問題
• アルゴリズムの能率の境界線
• ‘‘intractable’’な問題
– Encoding Scheme と計算機モデルの影響
– “reasonable”な Encoding Scheme
– “reasonable”な計算機モデル
“intractable”な問題
• 問題が“intractable”であるとは、その問題を解く多
項式時間アルゴリズムが存在しないときをいう。
• 多項式時間アルゴリズム：
– Time complexity function を多項式で抑えることができる
アルゴリズム
• Time complexity function は、
– Encoding Scheme
– 計算機モデル
に依存する。
Encoding Scheme と 計算機モデル
の影響
• 問題が“intractable”であるかどうかは、 Encoding
Scheme と計算機モデルに依存するか？
• Encoding Scheme と計算機モデルを、それぞれ
– “reasonable”な Encoding Scheme
– “reasonable”な計算機モデル
に制限すれば、問題が“intractable”であるかどう
かに影響しない。
“reasonable”な Encoding Scheme
• 例として、インスタンスがグラフ：
G = (V,E)
のときを考える。
• 例：右図のグラフの場合
V1
V = {V1, V2, V3, V4}
E = {(V1,V2), (V2,V3)}
V2
V3
V4
“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
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
“reasonable”な Encoding Scheme
• “reasonable”の意味するもの：
– 各インスタンスの encoding は簡潔であり、必要
のない情報は詰め込まれていない。
– 各インスタンスに含まれる数字は二進（または十
進，八進など、１以外の固定進）で提示されてい
る。
• これらの条件を満たす Encoding Scheme に制限
すれば、与えられた問題が“intractable”かどうか
の決定には影響しないだろう。
“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))
－
“reasonable”な計算機モデル
• これらの計算機モデル上では、アルゴリズムの複雑
度は、多項式的かどうかの観点から見れば同じで
ある。
• ここでの“reasonable”の意味するものは、
「単一時間内にこなせる仕事の総量に、多項式の
限界があること」
である。
• 例えば、勝手に並列処理を行う能力を持つような計
算機モデルは“reasonable”ではない。
Encoding Scheme と 計算機モデル
の影響
• “reasonable”な Encoding Scheme ：
– なるべく短い長さの文字列を出力する。
– 出力する文字列の長さは、多項式的以上には異ならない。
• “reasonable”な計算機モデル：
– 現実のコンピュータに近い。
– 多項式的かどうかの観点から見れば、アルゴリズムの複
雑さは異ならない。
• Encoding Scheme と計算機モデルに対して、この
ような制限をおけば、問題が“intractable”であるか
どうかに影響しない。
多項式時間アルゴリズムと
“intractable”な問題（まとめ）
• アルゴリズムの能率：
– 多項式時間アルゴリズム ＝ 能率的
– 指数関数時間アルゴリズム ＝ 非能率的
• “intractable”な問題
– 問題を解く多項式時間アルゴリズムが無いこと。
– Encoding Scheme 及び計算機モデルについて
は、“reasonable”なものに制限することで、問題
が“intractable”かどうかへの影響を取り除くこと
ができる。
© Copyright 2024 ExpyDoc
