評価の改良
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2021/06/24 10:07 UTC 版)
全体の時間を支配しているのは、第5ステップの時間であり、ひいては r {\displaystyle r} の大きさである。したがって、実は r {\displaystyle r} は ⌈ 16 log ( n ) 5 ⌉ {\displaystyle \lceil 16\log(n)^{5}\rceil } よりも小さく定まるということを証明できれば、計算量の評価を改善することができる。 篩理論より r = O ( log ( n ) 3 ) {\displaystyle r=O(\log(n)^{3})} であるということが分かるので、実際にはアルゴリズムは O ~ ( log ( n ) 7.5 ) {\displaystyle {\tilde {O}}(\log(n)^{7.5})} で動作する。 更に、いくつかの証明されていない仮説を認めるならば、 r {\displaystyle r} の評価をより小さくできる。 アルチン予想を認めるならば r = O ( log ( n ) 2 ) {\displaystyle r=O(\log(n)^{2})} である。 ソフィー・ジェルマン素数の密度予想が正しいと仮定すれば、 r = O ~ ( log ( n ) 2 ) {\displaystyle r={\tilde {O}}(\log(n)^{2})} である。 これらの仮説はともに一般リーマン仮説を認めれば証明できる。多くの数学者がリーマン仮説は正しいと信じていることを考えれば、 r = O ( log ( n ) 2 ) {\displaystyle r=O(\log(n)^{2})} つまり、AKSアルゴリズムの時間的計算量が O ~ ( log ( n ) 6 ) {\displaystyle {\tilde {O}}(\log(n)^{6})} である見込みは高い。
※この「評価の改良」の解説は、「AKS素数判定法」の解説の一部です。
「評価の改良」を含む「AKS素数判定法」の記事については、「AKS素数判定法」の概要を参照ください。
評価の改良
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2022/07/26 18:43 UTC 版)
スキューズの与えたこれらの見積もりは非常に大きいため、より小さな評価を与える研究が進められた。それは、コンピュータを用いてリーマンゼータ関数の零点を計算することによって行われる。Lehman (1966) が示したところによると、1.53 × 101165 から 1.65 × 101165 の間に π(x) > li(x) となるような整数 x が連続して 10500 個以上ある。H. J. J. te Riele (1987) は上からの評価を約 7 × 10370 にまで、Bays & Hudson (2000) は約 1.3983 × 10316 にまで下げ、その付近に π(x) > li(x) なる x が存在することを示した。 一方、Rosser & Schoenfeld (1962) は、x < 108 においては常に π(x) < li(x) であることを示した。この記録は Brent (1975) によって 8 × 1010 にまで、Kotnik (2008) によって 1014 にまで更新された。 正確にいつ初めて π(x) が li(x) が追い抜くのかは、未解決の問題である。それどころか、π(x) > li(x) となる具体的な x の値はひとつも知られていない。 Wintner (1941) は、π(x) > li(x) なる x の割合は正であることを示し、Rubinstein & Sarnak (1994) はその割合がおよそ 0.00000026 であることを示した。
※この「評価の改良」の解説は、「スキューズ数」の解説の一部です。
「評価の改良」を含む「スキューズ数」の記事については、「スキューズ数」の概要を参照ください。
- 評価の改良のページへのリンク
