PRIMES is in P

今やっているゼミの最終的な目標は、 PRIMES is in P を読んで実装してみようというものだ。これは去年発表された計算量理論分野の画期的な論文で、画期的であるにもかかわらず内容は易しくて学部レベルの知識で読める、と評判のものだ。まさにコロンブスの卵という表現が相応しい発見であり、ゼミで扱うにはある意味で適当な材料だ。

うちの数学科では3年次までの科目では計算量理論は殆ど扱っていないので、ゼミでは前期に計算量理論の入門的教科書として「 アルゴリズムと計算量入門 」を読んで、後期に元論文を読むことになっている。進度はあまり速くない。ぬるいゼミである。今年はGID関連で結構時間を喰うからゼミに全力投球はできないだろうと思ってそういうゼミを選んだのだのだし、先生もゼミ生もみんないい人だから良いのだけれど。

去年の秋にgoogleで調べた限りではまだこの論文を日本語で解説したサイトはないようだった。そこで、適宜解説を書いてうちのサイトで公開しようかと思っていたのだけれど、今調べたら 多項式時間素数判定アルゴリズム というサイトがある模様。私は元論文を読むのを楽しみにしているので(推理小説のネタバレをされたくないのと同じ心理で)このサイトは詳しくは読んでいないけれど、結構わかりやすそうな感じではある。

まぁ、いいや。うちはうちで書いてみよう……。とりあえず、今すぐあの論文を理解したい方は上記のサイトがおすすめです

2004年5月現在、とりあえず、私なりの説明を書き始めた状態。