# [読書メモ] Computers and Intractability 1

by Garey and Johnson

この文章は同タイトルの私的まとめである.

## 1 Introduction
<!-- 1.1はお話. 1.2から1.5に関して, この本で扱う言葉の定義がされている. -->

1章全体の目的は,
- "inherently intractable" な問題と,
- 問題が "equivalent" difficulty を持つ

とは, それぞれどういう意味なのか, を示すことである.

以下では, そのためのより基本的な言葉の定義をまず行う.

### 1.2 Problems, Algorithms, and Complexity

この節では, *Problems*, *Algorithms*, *Complexity* に関してそれぞれ定義を行っていく.

#### Problems
*Problems* とは, 以下の2つによって定義される.
1. その問題を記述するために必要なすべてのパラメータ
2. 問題の解が満たすべき性質に関する記述

その問題のパラメータを具体的に設定して得られるものを問題の *Instance* と定義する.

##### Traveling Salesman Problemの例
- 問題のパラメータ
- 都市と, 都市間の距離
- 解
- 経路のコストを最小にするような, 巡回する都市の順番

問題のパラメータとして具体的な数値が与えられたものがTSPのインスタンスというわけ.

#### Algorithm
*Algorithm* とは, 一般には, 問題を解くための段階的な手続きである. 具体的には, 何か特定の言語で書かれたコンピュータプログラムと考えられる.

アルゴリズムが問題 $\Pi$ を解くとは,
- そのアルゴリズムが $\Pi$ の任意のインスタンス $I$ に適用でき,
- 常にインスタンス $I$ の解を求めることができることが保証されている
ときのことを言う.

#### Complexity

問題の(時間的)複雑さ(Complexity)を記述するに当たって, インスタンスのサイズと時間的な複雑さを関連付けたい.

そのためには, その問題のインスタンスに対する入力(パラメータ)ってどう表現されるんですか, ということに気をつけないといけない.
その表現方式を *encoding scheme*とする.

また, 問題 $\Pi$ のインスタンス $I$ に対する入力長(*input length*)とは, 問題 $\Pi$ のencoding schemeによって得られる $I$ のパラメータのシンボル数として定義され, これがインスタンスのサイズとなる.

*time complexity function*は, インスタンスに対するパラメータの入力長(*input length*)に対して, アルゴリズムがそのインスタンスを解くのに必要な計算量の上界を表す.

問題の時間複雑度とか, 入力長, encoding schemeに関してなんで考えないといけないのか? については, 次節の1.3でちゃんと議論されてる.

### 1.3 Polynomial Time Algorithms and Intractable Problems
本節では, 時間的複雑さを考えるに当たって, "良い"アルゴリズムとは何か? また, "intractable"な問題ってどういうことなのか? についての話をする.
> 形容詞に"な"をつけるのって気持ち悪いなぁと思ってきた...

#### "efficient enough"と"too inefficient"を区別する
じゃあ何が"efficient enough"で何が"too inefficient"なんですか, という話だけど, これらは"多項式時間アルゴリズム"なのか, それとも"指数時間アルゴリズム"という風に区別される.

ここらで辺で$\mathcal{O}$-記法の話が出てくる.

##### polynomial time algorithm
*polynomial time algorithm*とは, アルゴリズムの入力長$n$に対して, time complexity functionが$\mathcal{O}(poly(n))$となるアルゴリズムとして定義される($poly(n)$は$n$の多項式関数).

##### exponential time algorithm
time complexity functionが上のpolynomial timeの上界を持たないようなアルゴリズムを*expoenetial time algorithm*と呼ばれる.

(上の定義では, $n^{\log{n}}$のような, 通常では指数時間アルゴリズムとされていないnon-polynomial time algorithmも含まれる.)

:::warning
ここでちょいと気になったことがある.

$n^{\log{n}}$が多項式時間でない, というのはまぁわかるんだけど, 指数時間アルゴリズムじゃないって人々はどうやって証明するんだろうという議論をした.

任意の$l>1$に対してある$n_0 > n$が存在して, そのような$n$に対して$l^n > n^{\log{n}}$が成り立つことを示せれば嬉しいんだけど,
研究室で議論してみてもうまい解決方法が見つからず, 対数をとって
$$
\lim_{n \to \infty} \frac{n \log{l}}{\log^2{n}}
$$
が無限に発散すればええかぁ(ロピタルの定理を使えば言えそう)みたいなザルな理解しかできていないため, 誰かコメントくれ.
:::

じゃあ指数時間と多項式時間のアルゴリズムでは, どう差があるんですか, みたいな表が7ページに書いてあって, 問題のサイズが大きくなると多項式時間アルゴリズムとし数時間アルゴリズムでは計算コストが桁違いだよね, という話をしている.

とは言っても, 計算機の高速化によっても実時間としての計算コストは変わってくるじゃん！と思う人もいるかもしれないが, 8ページの図では, 処理速度が増加した時にもともと解けてた問題のサイズに対して, どれくらいのサイズの問題が解けるようになりますか, という表も載せてくれている.

ここまでの指数時間と多項式時間のアルゴリズムに関する性能の比較から, なぜ多項式時間アルゴリズムの方が嬉しいのか, また, そのような区分をすることがinherent intractabilityの話とかNP-completenessの話に繋がってくるんだよという話をしてくれてる.

##### intractive
以降では, 問題が*intractive*とは, その問題を解くことができる多項式時間アルゴリズムがない場合のことをいう(やっとintractiveが定義された！).

かと言って, 先ほどのpolynominal time algorithmsとexponential time algorithmsの間には結構例外的なことが起こりうる(e.g., $n \le 20$の場合において, $2^n$のアルゴリズムは$n^5$のアルゴリズムよりも性能がいいよね?)
まぁこんな感じの例外というのはいくらでも作れるわけ.

更に, exponential time algorithmsだからと言って, 実際に動かした時にカス！w みたいなアルゴリズムばっかりって訳ではない. 前述の定義の通り, 時間複雑度というのは, *worst-case*(その問題の全インスタンスに関する, 最悪の場合)の話だからだ.

よく知られるアルゴリズムとして, 線形計画における単体法はexponential algorithmなんだけど, 実際にはより早く動くことが知られている. あとは, ナップザック問題に対する分枝限定法なんかも良く解けることが知られている.

:::info
これを読みながら, 確かにpolinomial time algorithmsだって, クイックソートは平均計量$\mathcal{O}(n \log{n})$だけど, 最悪計算量は$\mathcal{O}(n^2)$ですしねぇという話をしてた.
:::

とは言ってもworst-caseでは難しいんだけど, 実際にはよく動くアルゴリズムは稀である(僕は実際にはよく動くアルゴリズムばかり勉強してきていたので, 稀だというのが驚きだった. そりゃそうか).

exponential time algorithmsでもよく動くアルゴリズムもある一方で, polynomial time algorithmsだってなんでもいいってわけじゃない. 例えば, $n^100$のアルゴリズムや, $10^99 n^2$のアルゴリズムなんかは, いくらpolynomialだからと言っても許せない気持ちになる.

じゃあ, 問題を効率よく解けるような, "provably efficient"な多項式時間アルゴリズムというのを決めてやろう, ということで, 本書では最悪でも次数が2か3くらいで, アルゴリズムの実行時間に馬鹿デカい係数が隠れていないようなもの, としている.

#### encoding scheme
encoding schemeの話に戻る. 問題を表現するにあたって, "reasonable"なencoding schemeを考える.

問題の表現の仕方によって, input lengthが変わってきちゃうので, 何か条件を設けて, 問題を考える際に扱いやすい形で入力を表現しようというわけ.

本書でいう"reasonable" encoding schemeとは, 以下の条件を満たすencoding schemeのことをいう.
1. インスタンス $I$ のencodingは簡潔で, 不要な情報やシンボルで埋められていない.
2. インスタンス $I$ に与えられる数は, 2進数, 10進数, 8進数などの, 1以上の固定された底で表される.

こういう風にencoding schemeを決めてあげれば, 問題がintractiveかどうかというのは, どのencoding schemeを使うか, ということと独立なものとして考えられるわけ(encoding scheme毎にその入力長が大差ないと考えられるから).

10ページの図1.4に重みなし無向グラフ$G = (V, E)$のインスタンスが与えられた時の, encoding scheme毎の入力長が表でまとめられていて, 例があって良い.

また, 同ページの図1.5には図1.4のencoding schemeと入力長の一般的な関係をLower BoundとUpper Boundに関して表にまとめてある. Lower Boundに関してはそのまま数えるだけで, Upper Boundに関しては, グラフの頂点の添え字が10進数になっているので, その分増えていることがわかる(ちょっと多めに見積もりすぎな気もする).

#### computer models
同様の議論が計算機モデルの選び方によっても言えるよね, というのが11ページの図1.6 に載っているんだけど, ここら辺はオートマトンの話よくわからんのでスキップ(garey and johnsonはHopcroftの本読まんでもNP-completeまでたどり着けるからええで！ってオススメされたのに...グスン)

### 1.4 Provably Intractable Problem
さっきは多項式時間アルゴリズムと指数時間アルゴリズムの話をして, 特によく動くProvably efficientアルゴリズムの話だった.

じゃあ, 今度はIntractable Problemに関してちゃんと議論しようね. というのが本節の内容.

#### Intractabilityの2つのケース
先ほど定義したIntractabilityとして, 2つの場合が考えられる.
1. 解を見つけるのに指数時間要するくらい難しい問題
2. 解自体がとても大きく, 入力長の多項式関数で表せないくらいの長さの出力となる問題

1は想像しやすいけど, 2ってどういうこと??という人のために, 本書ではわかりやすい例を示してくれている.
例えば, 巡回セールスマン問題(TSP)の経路全体がある値$B$よりも大きくなるか小さくなるか, という問題だ. これは経路全てを列挙する必要があり, これは多項式時間アルゴリズムでは解けない.

後者のような問題は現実的ではないため, 以降では前者の問題に関して扱うこととし, また, 解の大きさは入力長の多項式関数で表すことができるものとする.

#### Undecidability and Decidability
はじめに決定不能問題に関して例示されている.
決定不能問題に関しては, [ここ](http://iso.2022.jp/math/tsudoi/10/slide.pdf)とかが詳しい(少なくともこの本に例示されているようなものに関しては載っている).

こう言った問題はより強い意味でintractableだよという話.

次に決定可能でintractableな問題に関するサーベイみたいなものが載っている. NP-completenessの話とかが出てくるんだけど, ここら辺の詳しい話は2章でしてくれるらしい.

#### Provably Intractable
今日におけるintractableな問題ってのは2種類に分けられて, "undecidable"か, "non-deterministically"にintractableであるという話.

### 1.5 NP-Complete Problems
そろそろいい感じの話になってくる. 人々が難しい問題を難しいと証明するために, また, 難しい問題同士の関係を表現するためにどういうことをしてきたかという話がざっくりとされている.

問題の関係を表現する主な操作は, 帰着(reduce)という, 問題$\Pi_A$のインスタンス$I_A$を, 可換な問題$\Pi_B$のインスタンス$I_B$に変形させる操作だ. この操作には, $\Pi_B$を解くアルゴリズムを$\Pi_A$を解くアルゴリズムに変換するという意味がある.

#### NP-completeness
ここら辺から種々の問題の帰着の歴史や, NP-Completenessの話になり, Cookの"The Complexity of Theorem Proving Procedures"(1971)が紹介されている.

1つめに, Cookは"多項式時間帰着可能"であることを強調した. これによって, 帰着先の問題を解く多項式時間アルゴリズムがあれば, 帰着元の問題を解く多項式時間アルゴリズムに変換することができるからだ.

次に、彼はクラスNPの問題に注目した.

3つめに, 彼はクラスNPに属する充足可能性問題が, 他のクラスNPに属する問題から多項式時間帰着可能であることを示した.

あとは諸々いろんな人の業績が載ってる. Cookに続いてKarpが, TSPを含む多くの組み合わせ問題の判定版問題が充足可能性問題と同じくらい難しいことを示した.

この辺で, クラスNPに属する問題のうちで, もっとも難しいと考えられている問題が*NP-complete problems*って名付けられたらしい. ようやく本題に入れそうな予感がしてきた.

あとは, NP-completeな問題がintractableなのか?という疑問が残されるわけだ.