ABC予想が解かれたかもしれんぞ!at MATHABC予想が解かれたかもしれんぞ! - 暇つぶし2ch■コピペモード□スレを通常表示□オプションモード□このスレッドのURL■項目テキスト800:132人目の素数さん 12/09/24 09:10:46.25 wikipediaくらい見たら? 801:132人目の素数さん 12/09/24 09:34:13.63 ラジアンだろうjk 802:132人目の素数さん 12/09/24 10:07:23.37 おそらくABC予想から導けそうな範囲よりずっと広い範囲のディオファントス方程式の解が 宇宙際幾何学によってこれから分かっていくだろう 803:TTT 12/09/24 10:50:58.72 >>796-797 以下は別スレのレスと加筆修正したもの。 有益な情報のためこのスレに転載します。 計算量クラスの種類はいくつあるのかと問われて... 1000どころか可算無限個はあります。 既にAC_iとかTC_iとか多項式時間階層の無限列が入ってますし。 基本的には、 (1)抽象機械、(2)領域、(3)時間、(4)オラクル の4つを設定するのでこれらを掛けた量だけ少なくともあります。 抽象機械とはチューリング機械(これだけでも決定性や非決定性や交替制や確率や量子)等が代表例で、他にも無数の抽象機械があります。 さらには述語論理に何々の記号を加えただとか、何々のパターンを持つ回路だとかまで入ります。 同じ機械でも領域と時間を制限することで色々変わってきます。 時間や領域の制限は対数とか指数とか2重の冪とかの単位で考えることが多いです。 面倒なのは、計算機の強さが時間や領域の制限と綺麗に相関しないところですね。 ある時間以上ではほとんど計算能力が向上しない状況、その逆の状況とかがあります。 また時間を自然数で区別すればはたまた自然数個の時間によるクラス分割が発生します。 そしてこれにオラクルという計算に別のクラスの補助を使用することを考えます。 Pをオラクルに持つPをオラクルに持つ...と、ここでも可算無限個のクラスが発生します。 しかもほとんどのクラスが潰れない(一致しない)。 P≠NPもほぼ間違いないと考えられていますし。 こう考えると計算量クラスの定義は<M、t、s、O>といった 抽象機械M、時間t、領域s、オラクルOの対として定義したほうがいいですよね。 計算量理論と述語論理等の記述(計算)能力まとめ。 http://people.cs.umass.edu/~immerman/descriptive_complexity.html 現在の複雑さの階層マッピング http://www.math.ucdavis.edu/~greg/zoology/diagram.pdf 名称付きのクラスのリスト http://qwiki.stanford.edu/index.php/Complexity_Zoo 次ページ最新レス表示レスジャンプ類似スレ一覧スレッドの検索話題のニュースおまかせリストオプションしおりを挟むスレッドに書込スレッドの一覧暇つぶし2ch