【大金持ち?!】1億円の入手方法 知った!!

最終更新日

ミレニアム懸賞問題のうちの,P≠NP予想の話です.

クラス\(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)

  1. 次式を満たす問題 \(X\) を\(NP\)-困難という.
    \(\forall L \in NP \,[L \leq^{\mathrm{P}}_{\mathrm{m}}X]\)
  2. さらに次式も満たす問題 \(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予想,最前線
初心者が読んだにしては上出来じゃないでしょうか!

面白かった!

コメントを残す

%d人のブロガーが「いいね」をつけました。