複雑さについて（７） 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といった、比較的小さな数字で特徴付けられるというのだ。
この複雑性に関する投稿の中で述べた、チェイティンの不完全性定理の示す、我々人間が（機械でも同じことだ）複雑さにチャレンジする時の、「複雑さの壁」（しかも、小さな数字で特徴付けられる）と同じような問題が、計算量の理論の中でも見つかったということだと思う。
ビーバー数についてのトピックは、以前の僕の次の二つの投稿を参考にしてほしい。
どうやっても計算できない数は、PであれNPであれ、計算可能な数より、複雑である。
コメント
コメントを投稿