ガロア第一論文と乗数イデアル他関連資料スレ5

[過去ﾛｸﾞ] ガロア第一論文と乗数イデアル他関連資料スレ5 (1002ﾚｽ)
上下前次1-新
通常表示 512ﾊﾞｲﾄ分割ﾚｽ栞
抽出解除ﾚｽ栞

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索歴削→次ｽﾚ栞削→次ｽﾚ過去ﾛｸﾞﾒﾆｭｰ

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

271: １３２人目の素数さん [] 2023/07/03(月) 07:07:17.16 ID:x5daDujY

>>269
ありがとうございます
スレ主です
これは謎のプロ数学者さんかな

＞圏論を使ったら数学の全知識が千頁の書物の記述に圧縮できるというようなことはまず期待できない

多分、ある分野やある手法に対しての加速定理（下記）を提供する能力が、圏論にはあるのではと思っています
（一階述語のZFC vs 圏論（二階述語）かも）
下記 ゲーデルの加速定理：弱い形式的体系では非常に長い形式的証明しか存在しないが、より強い形式的体系では極めて短い形式的証明が存在する
ここまでは、期待できるかも。ある分野では
例えば、層の理論も、（証明論の）一種の加速定理かもと思っています

https://ja.wikipedia.org/wiki/%E5%8A%A0%E9%80%9F%E5%AE%9A%E7%90%86
加速定理
計算複雑性理論における加速定理（かそくていり、英: speedup theorem）は、ある問題を解く算法に対し、同じ問題をより早く解く算法（また一般に、使用する資源がより少ない算法）の存在を示す定理である。
例
例として回文（palindrome）を認識する1-テープチューリング機械を考える。
略
同じ問題を
O(n) で解く次のような2-テープチューリング機械が考えられる。
種々の加速定理
チューリング機械に関する線形加速定理は、ある時間［ないし空間］計算量
f (n) のチューリング機械を与えると、 同じ問題を解く時間［ないし空間］計算量
c f (n) のチューリング機械が存在することを示した定理である（ただし
n は入力の大きさ、
c は正の定数）。

ブラムの加速定理は、時間計算量
\mathrm O (f (n)) の算法があれば、時間計算量
\mathrm O (\log f(n)) の算法も存在するような問題の存在を示す。この結果はブラムの加速定理の特別な場合である。この定理は時間計算量に限らずブラムの公理を満たす任意の複雑性の測り方に対して成り立つ。加速の度合いも計算可能関数の範囲で自由に指定できる。上の主張は複雑性測度として時間計算量を取り、加速関数を
r(x, y)=2^y とした場合に相当する。

量子コンピュータに関する2次関数的加速定理は、決定性コンピュータが時間計算量
O(f(n)) で検索が実行できるなら、量子コンピュータなら同一の検索が時間計算量
O(\surd f(n) ) で実行できることを示した定理である

つづく

http://rio2016.5ch.net/test/read.cgi/math/1687778456/271

上下前次1-新書関写板覧索設栞歴

ｽﾚ情報赤ﾚｽ抽出画像ﾚｽ抽出歴の未読ｽﾚ

ぬこの手ぬこTOP 0.042s