- 535 名前：TTT [2012/09/21(金) 18:50:20.81 ]
- >>531
ちなみに現在の複雑さの階層ってのは
www.math.ucdavis.edu/~greg/zoology/diagram.pdf
ここまで発展している。
PとかNPってのは記述可能な文のクラス、つまり集合というか全体みたいなもので、
文系の方にも知られているチョムスキー階層なんかも入ってくるよ。
あと一階論理で記述可能な文の全体とかね。
ほとんど解決してなくて解決の糸口さえ想像がつかないって状況。
現代数学で最も壮大かつ広範な研究分野だね！
qwiki.stanford.edu/index.php/Complexity_Zoo
なにしろクラスの種類は500近いからね、一体何世紀後に全てが解決するやら。
