複雑さについて(7) PとNP



先に、多項式時間で計算できない数は、多項式時間で計算できる数より複雑であると書いた。
計算量の観点からの複雑さの階層については、Aaronsonの次の図が参考になる。https://goo.gl/eLrIS7 
多項式時間で計算できる複雑さを、Polynomial-Timeの頭文字をとってPで表すのだが、NPというのは、Non-Polynomial-Time の略ではない。Nondeterministic Polynomial-Timeの略だ。
NPを多項式時間では計算できない複雑さだと、誤解している人も多いのだが、そもそも、このNPのネーミングが、よくないのだと思う。
下の図を見れば、Pの外側全体(多項式時間で計算できないもの)が、NPにはなっていないことがわかるだろう。ある問題が、正しいとわかっている時に、その検証が多項式時間でできるものをNPと呼ぶ。
ある数が、二つの素数の積に分解できることを見つけるのは難しいが、二つの素数の積がある数になることは、簡単に(多項式時間で)計算できる。だから、素因数分解の問題は、Pかどうかはわからないが、NP問題である。(実は、素因数分解が、多項式時間で計算可能なことは、最近になってわかった。)
今日、話したいのは、多項式時間で計算できない数には、とんでもなく複雑な数があるということ。
今年の4月に、Adam Yedidia と Scott Aaronsonは、BB(7910)が、普通の集合論の枠組みの中では決定できないことを証明した。BBは、Busy Beaver数という、複雑だが、きちんと定義された、しかも有限の数だ。
要するに、「有限」の値を持つのだが、どういう数学的な手段を持ちいても、我々が知り得ない数字があるということ。さらに、その限界が、7910とか1919といった、比較的小さな数字で特徴付けられるというのだ。
この複雑性に関する投稿の中で述べた、チェイティンの不完全性定理の示す、我々人間が(機械でも同じことだ)複雑さにチャレンジする時の、「複雑さの壁」(しかも、小さな数字で特徴付けられる)と同じような問題が、計算量の理論の中でも見つかったということだと思う。
ビーバー数についてのトピックは、以前の僕の次の二つの投稿を参考にしてほしい。
「Busy Beaver Game問題について」https://goo.gl/3QLsMc
「有限だが計算できない数の発見について」https://goo.gl/oV2b1o
どうやっても計算できない数は、PであれNPであれ、計算可能な数より、複雑である。


コメント

このブログの人気の投稿

マルレク・ネット「エントロピーと情報理論」公開しました。

初めにことばありき

人間は、善と悪との重ね合わせというモデルの失敗について