このＬＡ会誌でも特集を組むというので， 瀧本さんに，「是非にも」とお願いして紙面を頂きました． （なお， この原稿には， 多少の誇張，間違いなどがあります．ご容赦下さい．）
瀧本さんからの紹介にもありましたように， ゲーデル賞は， 過去７年間に雑誌掲載された理論計算機科学分野の論文のうちから， 最も優れたもの（２件以下）に対して与えられる賞です． 今回の戸田さんの授賞の対象となったのは，
です． ここでは， その論文がどんなにすごいものなのかを， （戸田さん風に？）検証していくことにしましょう．
１．戸田さんの結果の偉大さ
戸田さんのこの論文では， その題の示す通り， PP という複雑さのクラスの計算能力をもってすれば， 多項式時間階層程度のことはできてしまう， ということを証明しています． （以下では， この結果を単に「戸田の結果」と呼ぶことにします．） そう言われても， 「PP って何じゃ？」， 「多項式時間階層って何なの？」と思われる方も多いでしょう． それでは， 戸田の結果の偉大さにふれることはできません． だから， 用語の説明をさせてもらいます． 少し我慢して読み進んで下さい． （我慢できない人はしょうがありません． ご利益や少ないですが， 次の２へ進んで下さい．）
皆さん，NP という複雑さのクラスについては， 多少なりとも聞いたことがあると思います． これは， Yes/No の判定問題のクラスで， Yes 場合には， その証拠をもらえば， 「あっ，そうか」とすぐ納得できるような（Yes の）証拠がある問題のクラスです． たとえば， ハミルトン閉路問題などがその一つで， これは， 与えられたグラフ G に対して， ハミルトン閉路があるか否かを問う問題です． もし Yes（閉路あり）ならば，その閉路が（Yes の）証拠です． 一般的には， どんな NP-問題（NP に属している問題）Q に対しても， 次のような性質(1)を満たす述語 R_Q が定義できます． （正確には，そのような述語が定義できるのが NP-問題です．）
（１）任意の問題例 $x$ に対して
たとえば， ハミルトン閉路問題の場合には， 問題例 x はグラフであり， w が閉路のたどり方を表し， R_Q(x,w) は， 「w が x の正しいたどり方になっているか？」をチェックする述語となります．
言いかえると， NP-問題は， このような証拠をチェックする述語に対して， 与えられた問題例に対する証拠があるかないかをチェックする問題だといえます． 一方， 証拠の有無ではなく， 「いくつ証拠があるか？」と聞いた場合はどうでしょうか？ つまり， 証拠の数を聞くような問題です． これを #P-問題といい， すべての NP-問題に対して， この種の #P-問題を定義することができます． たとえば， ハミルトン閉路問題には， ハミルトン閉路の数を聞く問題が #P-問題として対応します． このような #P-問題のクラスを単に #P といいます． 実は， 先の PP は， このクラス #P とほとんど同じようなクラスです． という訳で， ここでは PP の代わりに #P で話しを進めます．
組合せ論的な多くの問題が， (1)のように特徴付けられるのですが， それでは言い表せないようなものもあります． そこで例えば， (2)のような形で Yes/No を判定するような拡張が考え出されました．
（２）任意の問題例 $x$ に対して
このように特徴付けられる問題を， Sigma^P_2-問題と呼び， その種の問題のクラスを Sigma^P_2 といいます． こうなると， 人間（数学者）のあさましい常で一般化を考えます． つまり， exists, forall, exists, ... と， quantifier を k 個つなげて Yes/No を特徴付けようという訳です． （ちなみに， そのような問題を Sigma^P_k-問題といいます．） このように， 有限個の quantifier で特徴付けられる Yes/No 問題を， 多項式時間階層の問題と呼び， その全体を多項式時間階層（polynomial-time hierachy，略して PH）と呼びます．
以上が用語の準備でした． （ここまで来れた人は幸せです． あなたには，戸田の祝福が待っています．）
さて， #P-問題は当然のことながら NP-問題の一般化です． ハミルトン閉路の数を答えられれば， ハミルトン閉路があるかないかの問題には， 当然， 答えられるでしょう． では， #P はどれほど強いのでしょう？ つまり， 証拠の数を答えられるとしたら， どれほどの計算ができるのでしょうか？ はたして， Sigma^P_2-問題など解けるでしょうか？ それができるということを示したが， 戸田の結果です． もっというならば， 任意の PH-問題， あるいは，任意の Sigma^P_k-問題が， ある #P-問題を使って解くことができるのを示したのです．
これだけでは， 戸田の結果の偉大さはよくわからないかもしれません． では， 少し考えてみて下さい． (1)のような証拠の数を数えることで， どうして(2)のような quantifier が 二重になった論理式を解くことができるのでしょう？ なかなか想像がつきませんよね． 実は， 証拠の数には， いろいろな情報が詰まっていたのです． そのことを最初に示した （そして， その情報の取り出し方を示した）のが， 戸田の結果だったのです． どうです．ありがたいでしょ．
２．戸田さんの証明の偉大さ
戸田さんの証明の偉大さは， 周到な準備の元に， エレガントに証明している点です． したがって， その周到な準備をクリアさえすれば， 証明はすーっと，脳に浸み渡るように理解できてしまいます． そういうきれいな証明ですから， 当然， 多くの人の心を打ちます．
たとえば， 戸田さんがこの結果を最初に投稿した FOCS では， その論文が， その年の FOCS の論文選定委員会（PC）の評価の中で， ダントツで一位だったそうです． PC 委員長だった Hartmanis 先生が， 私に， 「これは（MIT, UC Berkeley, Princeton 以外で 1 位だったのは） 過去数年間なかったことである」 と大変喜んで話してくれました．
実際， 私もこの証明に感動しました． 感動したあまり， 世界中の研究者仲間に， その証明（の概略）をいち早く速報しました． つまり， 戸田教の伝道者となったのです． 私にそうさせたのですから， まったく偉大ですね． （それで思い出しましたが， ある国際会議で， たまたま朝食を伴にしたかわいい女の子（当時）の研究者に， 「私は日本人研究者では戸田しか知らない」と言われ， そばにいた Peter van Emde Boas に， 「彼は B.T.(Before Toda) である」と弁護（？）された覚えがあります． 私はヨハネといったところでしょうか？）
３．戸田さんの論文の偉大さ
よくあることですが， 戸田さんの論文（以下，戸田の論文と呼ぶ）は， 長いこと未解決だった問題を解いたという意味で重要だったとともに， 計算の複雑さの理論へいろいろな影響を及ぼしました．
まず， 「証拠の数にはいろいろな情報が詰まっている」 という点です． 「それじゃ， 証拠の数には， どんな情報が詰まっていて， それらはどうやって取り出すことができるのだろう？」 という疑問が当然出てきます． その結果， 多くの研究者が証拠の数の研究を精力的に行ないました． その中から， たとえば Fortnow のクラス GapP などという優れた特徴付けが出てきました． この GapP は重要で， 今年の Computational Complexity Theory Conference (CCC'98)で， 多項式時間量子計算量クラス BQP の能力を特徴付けるためにも使われています． また， 多項式時間クラスと同様， 計算量理論で重要な対数領域クラスにおいても， 証拠の数の難しさが議論されて， 重要な結果を生んでいます．
次に PH 自身の研究です． 先ほど少々ちゃかして多項式時間階層（PH）のことを述べましたが， 実は， PH は単なる数学的な一般化の産物ではありません． 定数段数の AND-OR 回路に対応する大変自然な計算クラスなのです． したがって， 戸田の結果は定数段数の AND-OR 回路の能力に関する結果にも 深く関連しているのです． 実際， 戸田の結果を私から伝え聞いた Allender は， すぐさまそれを回路の話しに応用し， それを発端として， 垂井さんなどが重要な仕事をしています．
そして最後に証明手法そのものの影響です． 戸田の論文では， Valiant-Vazirani の isolation lemma をうまく利用し， また， ランダマイズドな計算とそうでない計算をうまく分けて議論しています． これも多くの人がまねることになった手法ですが， さらに重要なのは， 証拠の数を表す多項式を導入し， それをうまく定義することで議論を進めている点です． これは，現在，「戸田の多項式」と呼ばれていますが， このように， 多項式化して証明をする， という考え方自体斬新なものでした．
勝手な想像ですが， こうした考え方に影響を受けた Fortnow などが， Lund, Nisan の両氏と議論しあって， MIP $=$ NEXP という結果を出したのでは， そして， それが NP の PCP による特徴付けという結果につながっていったのではないか， という気がします． そうです． すべての主要結果は戸田の論文から出発しているのです．
４．さいごに
戸田さんがこの論文の核心について， 「ああでもない，こうでもない」 と考えていたのは， ちょうど今から１０年前の１９８８年の夏のＬＡの時だったと思います． あのとき， そのテーマをもっと勉強していて， 私の感覚が， もっと敏感に研ぎ澄まされていたら ...． 戸田の証明の伝道者となる前に， もっといろいろな結果を出すことができたのに， と悔やまれます． （もしかしたら， 今， あなたの隣で， うんうん考えている人が， すごいことを考えているかもしれませんよ．）
研究って，悩ましいですね． でも， その良さに素直に感動できて， 伝道者になれたことは幸せだったと思います．
ところで， 今から１０年前というと， 我々は笠井先生，小林先生，あるいは Book 先生などという， 優れた先生方に恵まれ， 非常に良い研究環境にあったように思います． そして今， 今度は， 我々が良い研究環境を提供していかなければならなくなってきました． まあ， どれほどのことができるかわかりません． でも， 「研究って悩ましい． けれども，とてもおもしろいんだ」ということを， 次からの世代に伝えていけたらと思っています．