昨日は対話でおしゃべりしながらふらりふらりと僧の不老１クエ進めていました。
瓦はとーじんぼーに空、火雷に天の蛇。

どれもめんどくさい。とーじんぼーで青龍ノックか火ってとこでしょうけど、どっちも徒党必須ですし。作るにしてももう遅かったですし、かといってとーじんぼーが救援祭りしやすいかってゆーとねぇ…。

ってわけでそろそろ鍛冶の方も不老２進めないとなーと思いつつ、進度合わせてしまった方が進めやすいのでとりあえず僧を鍛冶におっつかせてしまおうかと。

沙耶です。


そういうわけで書くことがありません。
で、コメント見てたら昔のエントリにコメついてて、ああ、じゃあちょっとこれでも書くかと。

乱数のお話。疑似乱数。

疑似乱数とは何か、って言うとですね。一見すると乱数のように見える、でも実は計算式で作ってる数列生成のことでございます。

乱数ってのは完全にランダムであり、一切の規則性を有しないものであり、これは人には生み出すことはできません。
なぜなら、予測不能であることが求められるからです。

一方で疑似乱数は計算によって生み出されているため、同じ計算式で同じ数字を放り込めば、全く同じ結果が出ます。
このため、数式と乱数種（シード）が分かれば、その先に生まれる数字を予測することができます。

一般には、この疑似乱数を持ってして、乱数と称しています。

ここまではそれほどわかりにくい話ではないと思います。
では。ちょっとステージを上げましょうか。

P≠NP問題、というのをご存じでしょうか。

たとえば疑似乱数生成機によってある数列が生み出されたとします。
その数列から、生成した数式を特定する方法はいったいどんな方法があると思いますか？

数列から特徴的な周期性を見つける？

うん、それは非常に単純な数式ならそうです。しかし、メルセンヌツイスタなどの高位乱数生成にはそんなもんありません。

じゃあどうするのか。

この世に存在するありとあらゆる数式に数字入れて計算してみて、同じ結果がでる数式を探す。

これが、現時点で可能な、そして確実な方法です。
ありえなーい。そうですね。ものすごく時間がかかります。

こういった、総当たりでしか解法を求めることができない問題のことをNP問題といいます。
一般的解法の存在しない問題。

最も身近なとこでは素因数分解がこれに当たります。
素因数分解とは、ある整数を素数の積で表現する分解方法で、約数の数、そしてその整数の持つ約数を取り出すことができます。

たとえば124。

これを素数の積であらわしなさい。といわれたら、どうするかというと、２から順番に√124までの素数で割って行くのがもっとも単純な解法です。

まず2で割ると62。まだ割れるので割ります。31。

31は素数ですから、124=2²x31¹で表現できることがわかります。
このとき、124の約数の数は素因数分解のべき数から求めることが出来、2は0～2までの乗数を取りうる、そして31は0～1の乗数を取りうるので、それぞれ3個と2個のべき数の値を取り得ます。

この積である6個が約数の総和です。

約数はもちろん、このべき数の組み合わせによって得られるわけで、2の乗数をa、31の乗数をbとすれば
a=0,b=0 のとき 1
a=1,b=0 のとき 2
a=2,b=0 のとき 4
a=0,b=1 のとき 31
a=1,b=1 のとき 62
a=2,b=1 のときが 124で自身となり約数は6個ですね。

これが素因数分解。じゃあ任意の数を素因数分解しましょうね、となったとき、流石に全部素数で割っていくとかだるいですよね。
ていうか素数公式もないのに、ものすごい大きな数の素因数分解をしようとすると、”√ｎまでの素数”がすでに知られているモノである必要があり、さらにはそこまでの数でほかに素数はないのかってのも調べないといけなくなったりもし得ます。

これらは、ものすごーーーーーーく時間がかかるっているか、総当たりするしか方法がありません。

とくに素数判定に関して。

こういった、総当たりするしか解きようがない問題のことです。

一方でP問題とは何か、っつーと、すでに公式が発見され、一般解法の存在する問題のことです。

たとえば二次方程式の解法。
ax²+bx+c={-b±√(b²-4ac)}/2a

これはもう何も考える必要もないですよね。aやbやcがどれほど大きい数であろうが、計算時間は極めて短い時間で終わることが予測できます。

これを、”多項式時間で解ける”といい、P問題という分類がなされます。
これを計算する時間は、ひとつの数字の計算にかかる時間がnとすれば、a*n時間で解けますよね。

これが一般解法と呼ばれるもので、PGなんかはアルゴリズムの計算量といった表現もします。

一方でNP問題は総当たりする必要があるため、その計算時間はn乗時間、あるいはn^n…..時間といった計算量になってしまい、あっという間に現実時間を振りきっていきます。


さて。


このときに、NP問題には一切の一般的解法が存在しないのでしょうか。

実は、NP問題とは、”一般的解法は存在しない”と証明されているモノはありません。
素数の生成公式は存在するかも知れませんし、存在しないかも知れません。
どちらかはわかりません。

＃もはや詭弁のガイドラインですねｗ

このため、NP問題である素因数分解も、もしかしたらすっごい簡単な公式があるのかも知れません。


そこで、こんな予想が出てきたのです。

NP問題には、必ずしも一般解法が存在するとは限らない。

これを、P≠NP予想といいます。


要はNP問題に、”一般的解法が存在しえない”ことを証明できるか。ってことです。
ちなみにこの問題、すーぱーこんぴーたーでおなじみクレイ社が懸賞をかけている、現代の数学の中でもトップクラスに答えがどうなるかが注目されている問題です。

現在ではほとんどの学者がP≠NPである、と考えていますし、P≠NPなのはほぼ間違いないだろう、と沙耶も思っています。

しかし、万が一、P＝NPであることが示される（NP問題がPに帰結する証明）がなされれば、たぶん世界中ひっくり返ります。
なぜなら、疑似乱数や暗号化の基礎である不可逆性暗号化、ハッシュ関数や通信の暗号化…これらのものは軒並みP≠NPであることを前提にしているからです。

とんでもなく長い時間をかけないと乱数生成の数式が得られないなら、それが実用的解析時間よりもはるかに長ければ、それは予測不能な乱数に（見掛け上は）見える、というのが疑似乱数の根底の思想です。

同様に暗号化も、解析にものすげぇ時間がかかるから（現実的に）破れない、というだけであって、それはあくまで数式で生み出しているのですから、無限の時間を使っていいならどんな暗号でも破ることはできます。
無限の時間とかいう無茶な要素が入ってるから、この暗号は破れませんよ、というのが強い暗号の証左になっているのです。

ところが、P≠NPではなく、P＝NPである、と証明された場合。

無限の時間を強要することは”不可能である”という証明に等しいのです。
がんばって公式見つければ、短時間でその問題を解くことができる一般解が存在する、ということになってしまいます。

多項式時間内に解決する解法が得られれば、あとは計算するだけです。
暗号理論の根底とも言える部分が崩れるのです。

さあ。この懸賞付きの大問題、あなたも挑戦してみませんか？

現在、クレイによって100万ドルの懸賞がかかっている問題は以下。ミレニアム問題とも呼ばれます。
・P≠NP予想
・ホッジ予想
・ポアンカレ予想（解決済み）
・リーマン予想
・ヤン-ミルズ方程式と質量ギャップ問題
・ナビエ-ストークス方程式の解の存在と滑らかさ
・BSD予想

このうち、ポアンカレ予想は解決しましたが、解決法への道筋を示し、現在では解決に最大の寄与をした、ということで解決者として扱われているベレルマンさんは数学のノーベル賞とも言えるフィールズ賞を辞退していますし、あんま賞金にも興味ない、といわれています。

残り6つ。いずれも、古くから数学者を悩ませる大問題。フェルマーの予想が解かれた今、P≠NPやリーマン予想は比較的理解しやすく、また素数という非常に魅惑的なものを取り扱うため、参加者も多い問題です。
リーマン予想は現時点で15億個くらいまでは予想通りであり、ただの一つの反例も見つかっていません。反例をひとつでも見つけるか、あるいは”反例は存在しえない”ことを証明するか。
こちらも「多分あってんじゃねーの」ってみんな思ってはいますが、無限数列の中でのたった15億個じゃねぇ…って言う人もいます。

まだまだ、世界はナゾだらけなのです。

ちなみにリーマン予想は量子力学とも深いつながりのある問題で、量子力学はこれらミレニアム問題に左右される点がいくつも存在しています。

リーマン予想はしょっちゅう「解けた！」って言いだす人がいるんですが、毎度間違ってたりします。
2004年にも「解けた！」って言ってる人がいますが、まだ検証作業は終わってないのかなぁ。
リーマン予想は化け物すぎて…アレなんですけどね…。問題が比較的理解しやすいにも関わらず、その根っこがものすごくでかいという…。

素数がらみの未解決問題としては、このほかにもゴールドバッハ予想というものもあります。
あ、ゴールドバッハ予想はさらに簡単ですよ。問題自体は。ほんと、問題を理解するのは中学生でもできます。

問題：4以上のどんな偶数も二つの素数の和であらわすことができる。と、俺は思う

ってだけです。

問題だけは馬鹿でもわかるほど単純なんでフェルマーに通じる問題ではあるんですがねｗｗｗｗｗｗｗｗｗｗｗｗ
どんなに計算しても反例でてこないし、確率的には数字が大きくなればなるほど成立しやすくなっていくため、「多分あってんじゃねーの」ってみんな思ってますがやっぱり証明できてません。

未来の数学者、立ち上がれ。