アカウント名:
パスワード:
もし元の素数が素数であることが (たとえばパ
決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ。ただ遅かっただけで。
またこういう嘘を平気で書くもんなあ。モデレートダウンもされてないし。元のコメントでリンクされている論文の冒頭にもはっきりと
In 1983, Adleman, Pomerance, and Rumely achieved a major breakthrough by giving a deterministic algorithm for primality that runs in (log n)O(log log log n) time (all the previous deterministic algorithms required expon
決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ。ただ遅かっただけで。 またこういう嘘を平気で書くもんなあ。
またこういう嘘を平気で書くもんなあ。
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
すいません、 (log n)O(log log log n)って O(log n) にはならないのですか?
そんなのは紀元前から出来ていますよ を肯定しているのでしょうか???
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
より多くのコメントがこの議論にあるかもしれませんが、JavaScriptが有効ではない環境を使用している場合、クラシックなコメントシステム(D1)に設定を変更する必要があります。
未知のハックに一心不乱に取り組んだ結果、私は自然の法則を変えてしまった -- あるハッカー
素人の質問 (スコア:0)
もし元の素数が素数であることが (たとえばパ
Re:素人の質問 (スコア:2, 参考になる)
-- 哀れな日本人専用(sorry Japanese only) --
Re:素人の質問 (スコア:0)
Re:素人の質問 (スコア:0)
またこういう嘘を平気で書くもんなあ。モデレートダウンもされてないし。元のコメントでリンクされている論文の冒頭にもはっきりと
Re:素人の質問 (スコア:1)
そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、多項式時間アルゴリズムということになってしまいますからね。
Re:素人の質問 (スコア:0)
すいません、 (log n)O(log log log n)って O(log n) にはならないのですか?
O(log n)なら桁数って思えるのですが。
あと、
> そう考えれば、x=2^n-1が素数かどうか判定するのにO(2^n)かかるアルゴリズムも、
> 多項式時間アルゴリズムということになってしまいますからね。
と書いているということは、
> 決定性の多項式時間で判定できるのは、そんなのは紀元前から出来ていますよ
を肯定しているのでしょうか???
例えば通常の10進数で考えて(2進数にしても基本的には
Re:素人の質問 (スコア:1)
たとえば、3からsqrt(n)までのすべての奇数で割ってみるという 一番素朴なアルゴリズムの計算量は、割り算が定数時間としてO(n^0.5)となります。ここで問題のサイズとしてnそのものをとれば、この素朴アルゴリズムは立派な多項式時間アルゴリズムと解釈できるわけです。
しかし常識的にはln nをサイズとして考えるべきなので、そうすると計算量はO(2^((ln n)/2))となり、桁数の指数関数となります。
Re:素人の質問 (スコア:0)
正しいのは(log n)^O(log log log n)です。だからO(log n)にはなりません。準指数関数時間であって多項式時間ではありません。