12/09/22 21:22:16.16
>>615
宮西正宜さんの代数幾何学をかなり昔にやったことがあります。
帰納法はあまり使いませんが、数学オリンピック的な難しさがあります。
>>616
そんなに深い話までは知りませんが、
入門と標準的な定理の証明においては通常の数学では考えられないほど長い証明が多いです。
ですから大抵のテキストは証明のアイデアしか述べられません。
>>617
1000どころか可算無限個はあります。
既にAC_iとかTC_iとか多項式時間階層の無限列が入ってますし。
基本的には、
（１）抽象機械、（２）領域の量、（３）空間の量、（４）オラクル
の4つを設定するのでこれらを掛けた量だけ少なくともあります。
抽象機械とはチューリング機械（これだけでも決定性や非決定性や確率や量子）なんかが代表例で、
他にもいくるも計算能力が異なる抽象機械があります。
さらには述語論理に何々の記号を加えただとか、何々のパターンを持つ回路だとかまで入ります。
同じ機械でも領域と時間を制限することで色々変わってきます。
時間や空間の制限は対数とか指数とか2重の冪とかの単位で考えることが多いです。
面倒なのは、計算機の強さが時間や空間の制限と綺麗に相関しないところですね。
ある時間以上ではほとんど計算能力が向上しない状況、その逆の状況とかがあります。
そしてこれにオラクルという計算に別のクラスの補助を使用することを考えます。
Pをオラクルに持つPをオラクルに持つ...と、ここでも可算無限個のクラスが発生します。
しかもほとんどのクラスが潰れない（一致しない）。
P≠NPもほぼ間違いないと考えられていますし。
ちなみに計算量理論の最上部の方にあるクラスRってのは
再帰的クラスでΔ^0_1とも書かれ、その上のREは再帰的可算クラスと言いΣ^0_1と書かれます。
こういった記述は再帰理論という分野で扱われ、
この上にさらに算術的階層や解析的階層やレヴィの階層というものが連なっています。
こちら側は全く別の手法で（計算機と言うより純粋数学的な手法）研究されます。