P is not NP?
また、引っ越すことになりました。去年の１２月に２年契約で今の部屋に引越しをしたばかりなのですが、事情があってこの冬の終わりくらいに京大の近くに引っ越します。引越しといっても今のアパートから自転車で１０分も掛らないくらいのところなのでなんてことないと言えばなんてこともないです。引越し先については書きたいことが山ほどあるのですが、理由があってそれも控えることにします。
しばらく前に、京都国立近代美術館の「エモーショナル・ドローイング展」をさっと見に行って、アートは基本的にＮＰ問題かもしれないな、と思いました。作家の好みに全人類が同じだと仮定すると、絵の良し悪しは見た瞬間に分かるからです。
ＮＰというのは Non-deterministic Polynomial time の頭をとった物で、日本語では非決定性多項式時間だとかなんとか訳すようです。ただ面倒なので普通はＮＰと呼ぶと思います。それから「ＮＰ問題」というのは「解が与えられたとき、それが正しいという検算が多項式時間で可能な問題」のことです。
多項式時間というのは、計算に必要な時間の関数が問題サイズを引数とした多項式で書けるという意味で、問題のサイズをS、計算時間をT(S)としたときに
T(S) = C1 + C2*S + C3*S^2 + C4*S^3 + … + Cn*S^n
; Cnは係数、*は掛け算^は累乗
で書けるような問題のことです。Ｓの５０乗とかが出てきたら大変な気がしますが、この多項式時間というのは「簡単に解ける」というくらいの意味合いで用いられます。本当に大変な問題は多項式時間では計算できなくて、
T(S)=e^S ; eは自然大数の底2.718281828...
みたいな感じで指数関数的に計算時間が爆発します。
この多項式時間で解ける、つまり「簡単な」問題をＰ問題というのですが、Ｐ問題とＮＰ問題は一緒なのかどうか、つまり検算が多項式時間で行えるような問題はその答えの導出も多項式時間でできるのかどうかというのが数学上最大の問題になっていて、未だ誰も証明に成功していません。たしか１００万ドルくらいの懸賞金が掛けられていたと思います。P⊆NPは明らかですが、逆の包含関係が成立しているのかどうかは分からない。
今のところ経験的に P≠NP であろうという予測がされていて、その一つの根拠に因数分解などを多項式時間でこなすアルゴリズムが発見されていないから、ということが上げられます。因数分解は小さな数なら簡単にできるけれど、大きな数になると多項式時間では計算できません。15の因数分解は瞬間的に3*5だと分かるけれど、167680の因数分解はそんな簡単にできませんよね。でも、3*5を計算して15を導くように、どんな大きな数の因数分解でも検算は簡単にできます（ただの掛け算ですから）。この因数分解の難しさというのは現代暗号のベースですが、もしもP=NPだとしたら、実は因数分解も多項式時間でできる方法（量子コンピュータは今想定していません。ここまで漠然と計算と書いていますが、普通のチューリングマシンで計算することを前提にしています）がどこかにある、ということになり、暗号の安全性はほぼなくなってしまいます。
このＮＰとＰが同じかどうかというのは、単に数学の問題ではなく、僕達の宇宙がどうして一見非可逆的にできているのかとか、そういうことにダイレクトに関わってくる問題にも見えます。
しばらく前に、京都国立近代美術館の「エモーショナル・ドローイング展」をさっと見に行って、アートは基本的にＮＰ問題かもしれないな、と思いました。作家の好みに全人類が同じだと仮定すると、絵の良し悪しは見た瞬間に分かるからです。
ＮＰというのは Non-deterministic Polynomial time の頭をとった物で、日本語では非決定性多項式時間だとかなんとか訳すようです。ただ面倒なので普通はＮＰと呼ぶと思います。それから「ＮＰ問題」というのは「解が与えられたとき、それが正しいという検算が多項式時間で可能な問題」のことです。
多項式時間というのは、計算に必要な時間の関数が問題サイズを引数とした多項式で書けるという意味で、問題のサイズをS、計算時間をT(S)としたときに
T(S) = C1 + C2*S + C3*S^2 + C4*S^3 + … + Cn*S^n
; Cnは係数、*は掛け算^は累乗
で書けるような問題のことです。Ｓの５０乗とかが出てきたら大変な気がしますが、この多項式時間というのは「簡単に解ける」というくらいの意味合いで用いられます。本当に大変な問題は多項式時間では計算できなくて、
T(S)=e^S ; eは自然大数の底2.718281828...
みたいな感じで指数関数的に計算時間が爆発します。
この多項式時間で解ける、つまり「簡単な」問題をＰ問題というのですが、Ｐ問題とＮＰ問題は一緒なのかどうか、つまり検算が多項式時間で行えるような問題はその答えの導出も多項式時間でできるのかどうかというのが数学上最大の問題になっていて、未だ誰も証明に成功していません。たしか１００万ドルくらいの懸賞金が掛けられていたと思います。P⊆NPは明らかですが、逆の包含関係が成立しているのかどうかは分からない。
今のところ経験的に P≠NP であろうという予測がされていて、その一つの根拠に因数分解などを多項式時間でこなすアルゴリズムが発見されていないから、ということが上げられます。因数分解は小さな数なら簡単にできるけれど、大きな数になると多項式時間では計算できません。15の因数分解は瞬間的に3*5だと分かるけれど、167680の因数分解はそんな簡単にできませんよね。でも、3*5を計算して15を導くように、どんな大きな数の因数分解でも検算は簡単にできます（ただの掛け算ですから）。この因数分解の難しさというのは現代暗号のベースですが、もしもP=NPだとしたら、実は因数分解も多項式時間でできる方法（量子コンピュータは今想定していません。ここまで漠然と計算と書いていますが、普通のチューリングマシンで計算することを前提にしています）がどこかにある、ということになり、暗号の安全性はほぼなくなってしまいます。
このＮＰとＰが同じかどうかというのは、単に数学の問題ではなく、僕達の宇宙がどうして一見非可逆的にできているのかとか、そういうことにダイレクトに関わってくる問題にも見えます。
