世界線航跡蔵

Mad web programmerのYuguiが技術ネタや日々のあれこれをお送りします。

2005年11月27日

PRIMES is in P, 6th ed.

あ、PRIMES is in PのAugust 2005 ver. が出てる。私がゼミで読んだのは3rdだから、あれから結構改訂したのね。

大枠は変わっていない(そらそうだ。変わってたらもっと話題になってる)ものの、ざっと見た感じでも記法が整理されたほかに、いくつか変更点がある。

  • rの上界が[log^5 n]からmax{3, [log^5 n]}に変わった。

Step 4の不等式が意味をなす範囲が少し限定される。私らが実験値から推測したのと大体大きさは合ってる。私らの実験値のほうがいくらか大きかったのは、オイラー関数あたりの実装がかなり甘かったからだろう。

  • LenstraによるAgrawal予想の否定。

古い版ではFuture Workとしてオーダーを大幅に下げる予想を提示してあったけれども、それは2003年3月にLenstraが偽であると証明した。そのことに言及している。でも、「それでも何かこの命題の変形で真になるものがあるかもしれない」と食い下がっている。

そう言えば、先生は冗談交じりに「Agrawal予想を証明できたら即、修士号あげるよ」と言ってたけれど、それからすぐにLenstraの論文が出てしまったのだった。

トラックバック

http://yugui.jp/articles/303/ping

現在のところトラックバックはありません

コメント

blog comments powered by Disqus

ご案内

前の記事
次の記事

タグ一覧

過去ログ

  1. 2016年07月
  2. 2016年01月
  3. 2015年09月
  4. 2015年08月
  5. 過去ログ一覧

フィード

フィードとは

その他

Powered by "rhianolethe" the blog system