【大金持ち?!】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予想,最前線 | ☓ |
面白かった!