LIX-th stone: New Horizons in Computing

２月２８日から３月３日まで、京都で行われたNew Horizons in Computingという国際会議に出席してきた。この会議は新世代の計算限界のキックオフ会議として開催された物である。この２１世紀の初めにあたって非常に魅力的なタイトルである。この会議では"計算"だけにとどまらず、いわゆる理論計算機科学のあらゆる分野の講演があった。ほとんどが招待講演とあって講演者のリストをみると著名な研究者達が名をつらねている。

その中でも面白かったのがLance Fortnow氏の"My Favorite Ten Theorems of the Past Decade."という物だ。彼の名前は以前から彼の"Computational Complexity"というweblogで知っていた。彼は1994年に、1985年から1994年の１０年間、彼がcomputational complexityという研究のコミュニティにいて記憶に残る１０個の定理をまとめている(ECCCへのリンク)。

そして2005年、1995年から2004年までの１０年に彼の記憶に残った１０個の定理をリストアップしている。

この２０個の定理を見直してみると１９８５年からこれまでのComputational Complexityという分野は理論計算機科学のいろいろな分野と密接に関わっていると言わざるを得ない。理論計算機科学の分野はどれをとってもCompuational Complexityとは切っても切れないという感じである。よって去年の年末からいっている理論計算機科学における大きな歴史の流れを学ぶ良い教材を得たような気分である。今後コツコツとであるがこの２０個の定理を学んでいきたいと思う。