【大金持ち？！】1億円の入手方法 知った！！
クラス\(P\)とは？
これが簡潔で最高に分かりやすい！(定理 3.2)
\(\displaystyle P=\mathrm{TIME}[ \,\, \ell^{\mathcal{O}(1)}]\)
ただし：
- \(\ell\) は問題例サイズ． (問題例 という日本語はこの本特有の用語だった気がする．一般的な数学の言葉では何て言うんだ？)
- クラス \(\mathrm{TIME}[\,t(\ell)]\) は，時間計算量の上界が \(\mathcal{O}(t(\ell))\) となる決定問題の集合．(定義 3.2)
- 関数\(f\)，\(g\)に対して \(f=\mathcal{O}(g)\) とは， \(\exists c\) と \(\exists d\) を決めたら， \(\forall n \geq d\) に対して \(f(n)\leq cg(n)\) が成り立つということ．(定義 3.1)
時間計算量，問題例サイズ，決定問題など，用語が未定義じゃ理解しようもないけど，それらは雰囲気で理解して！あるいは本を読んで！
…上の表示は厳密には「定義」ではない．定義はこう(定義 3.3)：
\(\displaystyle P=\bigcup_{p:\,多項式}\mathrm{TIME}[\,p(\ell)]\)
まずはこれが知りたくて本を買ったので，よく理解できて満足！
クラス\(NP\)とは？
クラス\(NP\)は，定義が十分に分かりやすい．(定義 3.7 の書き直し)
次式が成立するような決定問題 \(X\) をNP問題と呼び，NP問題の全体をクラスNPと呼ぶ．
\(x \in X \Leftrightarrow \exists w \,[\,|w|\leq q(\ell) \,\land \, R(x,w)=1]\)
ただし：
- \(\ell=|x|\)
- \(q\) は多項式
- \(R\) は \(X\) を解く多項式時間原始計算機
要するに，「正の問題例 \(x\) の証拠 \(w\) (~解) が与えられると，多項式時間以内で \(x \in X\) を確認できるような問題」のこと．
多項式時間原始計算機もこの本だけの用語だった気がする．アルゴリズムと雑に換言可能かな？
…日本語で言い換えてみると，こうなる：
\(\forall x \in X\) に対して \(\exists w\) があり， \(|w|\leq q(\ell)\) かつ \(R(x,w)=1\) が成り立つとき， \(X\) は \(NP\)問題である という．※
※否定も成立する必要がある．つまり， \(\forall x \notin X\) に対しては，どんな \(\forall w\) も \(|w|>q(\ell)\) または \(R(x,w)\neq 1\) ．
\(NP\)-完全
大変わかり易い．「クラス\(NP\)で一番難しい」とはよく言ったもの．(定義 5.2)
- 次式を満たす問題 \(X\) を\(NP\)-困難という．
\(\forall L \in NP \,[L \leq^{\mathrm{P}}_{\mathrm{m}}X]\) - さらに次式も満たす問題 \(X\) を\(NP\)-完全と言う．
\(X \in NP\)
1式に登場する 「\(\leq^{\mathrm{P}}_{\mathrm{m}}\)」は，多項式時間還元を意味する記号．1式の意味は「クラス\(NP\)に属するどんな \(\forall L\) に対しても，\(L\)から\(X\)への多項式時間還元が存在する」ということ．
多項式時間還元についての定義 (定義 5.1) は書かないけど，これを直感的に言えば「多項式時間である問題を別のある問題へ置き換えること」かなあ．
本当は\(\mathrm{P}\)と書きそうな気がする．つまり，イタリックではなくローマン体で書くべきかも．面倒くさいから\(P\)で書いちゃうけど．
理解度
ざっくりとこの本の理解度をまとめるとこんな感じでしょうか．基礎は分かったけど，しっかりした解析部分はよく分からなかったね…また読んだら分かるかもしれないか楽しみにとっておこう…
| 章 | 理解 |
|---|---|
| P≠NP予想とは？ | ○ |
| 「計算」を議論するために | ○ |
| 計算量クラス | ○ |
| 解析法#1 対角線論法 | △ |
| 解析法#2 還元 | ○ |
| 解析法#3 模倣 | ☓ |
| P≠NP予想，最前線 | ☓ |
面白かった！
