12/09/28 08:12:59.19
以下は別スレのレスと加筆修正したもの。
有益な情報のためこのスレに転載します。
計算量クラスの種類はいくつあるのかと問われて...
1000どころか可算無限個はあります。
既にAC_iとかTC_iとか多項式時間階層の無限列が入ってますし。
基本的には、
（１）抽象機械、（２）領域、（３）時間、（４）オラクル
の4つを設定するのでこれらを掛けた量だけ少なくともあります。
抽象機械とはチューリング機械（これだけでも決定性や非決定性や交替制や確率や量子）等が代表例で、他にも無数の抽象機械があります。
さらには述語論理に何々の記号を加えただとか、何々のパターンを持つ回路だとかまで入ります。
同じ機械でも領域と時間を制限することで色々変わってきます。
時間や領域の制限は対数とか指数とか2重の冪とかの単位で考えることが多いです。
面倒なのは、計算機の強さが時間や領域の制限と綺麗に相関しないところですね。
ある時間以上ではほとんど計算能力が向上しない状況、その逆の状況とかがあります。
また時間を自然数で区別すればはたまた自然数個の時間によるクラス分割が発生します。
そしてこれにオラクルという計算に別のクラスの補助を使用することを考えます。
Pをオラクルに持つPをオラクルに持つ...と、ここでも可算無限個のクラスが発生します。
しかもほとんどのクラスが潰れない（一致しない）。
P≠NPもほぼ間違いないと考えられていますし。
こう考えると計算量クラスの定義は＜M、ｔ、ｓ、O＞といった
抽象機械M、時間ｔ、領域ｓ、オラクルOの対として定義したほうがいいですよね。
計算量理論と述語論理等の記述（計算）能力まとめ。
URLﾘﾝｸ(people.cs.umass.edu)
現在の複雑さの階層マッピング
URLﾘﾝｸ(www.math.ucdavis.edu)
名称付きのクラスのリスト
URLﾘﾝｸ(qwiki.stanford.edu)
1001:１００１
Over 1000 Thread
このスレッドは１０００を超えました。
もう書けないので、新しいスレッドを立ててくださいです。。。