by R.Uehara (uehara@jaist.ac.jp)
LAの会誌31号で、私は勝手にはじめた『日の目を見なかった問題たち』と 銘打ったシリーズ物の第2回目をやらせてもらいました。そこでとりあげたのは 『倉庫番』という一人ゲームでした。そしてこの倉庫番を一般化し、 n×nの盤面に拡張したゲームを考え、このゲームの複雑さは PSPACE完全に違いないと書いてしまいました。 そして最後に
もし『倉庫番がXX完全である』ことが証明できたらどうかご一報下さい。
と呼び掛けておきました。本稿はこのお話の続編です。本稿の結論を最初に書 いてしまうと「この問題はやっぱりPSPACE完全でした」ということです。 なんとすでにFUN '98という 国際会議で Culberson 氏によって発表された、 既知の結果でした[Cul98]。 私と一緒に悩んで下さった方、一歩出遅れました。ごめんなさい。 ちなみに Culberson 氏の PSPACE 完全性の証明は『倉庫番でTuring Machine の計算を模倣する』という、王道とでも言うべき手法で行われています。 この論文の詳細な Technical Report が Web 上で 公開されていますが…[Cul97]。 彼は相当な gadget マニアに違いありません。
これだけで終わってしまってはあまりにもつまらないので、私がどのようにし て上記の結果を知り、そして文献を手に入れたか、を紹介しましょう。 そして昨今のインターネット上のデータ収集について、 私の個人的なノウハウもちょっぴり紹介します。 こういうのは私よりも、もっと詳しい方もいらっしゃるかと思いますが、 叩き台くらいに思っていただけると幸いです。 いい情報があったら教えて下さい。
ある日のこと、前回のLAの会誌を読まれた創価大学の小林孝次郎先生からメー ルをいただきました。小林先生のところに送られてきていた FUN '98 のプロ グラムの中に、どうもそういう結果がある、とのことでした。しかし FUN '98 の Proceedings を入手するのはどうも難しそうです。どうやって中身を確認 しましょう…。
FUN '98 のプログラムから、著者の Culberson 氏は Canada の Alberta 大学 の方だ、ということがわかりました。そこで Canada の Yahoo! から Alberta 大学を探し、Alberta 大学の中の学部をうろついた挙げ句、Culberson 氏のホー ムページを見つけました。そこからたどっていくと Technical Report の形で 公開されていた、上記の結果の全容を知ることができたわけです。所要時間は 20分くらいでしょうか…。
今回は比較的容易に、本人が結果を公開しているページを発見できました。 いつもこううまく行くわけではありませんが、最近はインターネット上で ごちゃごちゃと作業するだけで目的が達成できることが珍しくありません。 せっかくなので私のノウハウを紹介します。
例えば「Maximum Weighted Matching」に関する既存の結果 (今回のLAでこの話をするつもりだったのですが、 申し込むのを忘れました)を知りたい時、 みなさんはどのようにして調べていますか。図書館で行き当たりばったりで探し たり、読んでいる論文からイモヅル式に引っ張ってくる、というのも一つの手 ではあります。でも最近は Web 上のデータベースもかなり充実しています。 私が普段よく使っているのは、 The Computer Science Bibliography Collection という文献データベースです。 これはキーワードを与えるだけで、かなり多くの文献から該当するものを 探してくれます (たしかずっと前に、群馬大学の 山崎さんに教えてもらったような気がするのですが記憶があやふや…)。 前回の LA の会誌で紹介した倉庫番に関するいくつかの結果 ([MMH96,JS98])も、 ここで調べたものです。
最近はかなり多くの人が、自分の結果を Web で公開しています。既存の結果 を調べて、ある人が関連する論文を書いている場合、私はまずその人のホーム ページやメールアドレスを探します (自分の大学で文献を入手できる可能性が少ないので…)。 しかし上記のデータベースでは著者名はわかっても、所属機関などはなかなか わかりません。
ここで意外と役にたつのが、あの Lecture Notes in Computer Science シリーズのページです。 (最近ちょっと使い勝手が変わってしまって、登録が必要になってしまいまし た。登録そのものは無料なのですが、モノグサな私はサボっています。) このページの中には、著者名による検索機能があります。ですからその人が 最近 LNCS シリーズに載ったことがあれば、その文献の abstract などを見る ことができます。 そしてそこには、著者の所属や E-mail アドレスなどが書いてあります。 ここまでわかれば、その人の所属組織や、本人のホームページもだいたい 推測できます。もちろん本人に直接メールを書くこともできます。 私はこの手でずいぶんといろんな文献を入手しました。
最新の結果をパラパラと眺める、というのも、インターネット上のサービスで かなりなんとかなります。例えばElsevier では、刊行している雑誌のタイトルと著者名を 随時メールで送ってくれる ContentsDirect というサービスをやっています。ここに登録しておけば、例えば Theoretical Computer Science や Information Processing Letters などに何が載っているのか、 いち早く知ることができます。そして Electronic Access to Mathematics journals via Elsevier なんてところを利用すれば、さらなる情報を得ることもできます。 なかなか太っ腹です。
最近東工大の山崎君と元木君に、非常に強力な検索エンジン AltaVista を教えてもらいました。ここはとにかくなんでもかんでも検索できるそうです。 実際、SOKOBAN に関する Culberson 氏の結果も AltaVista なら 見つけることができました。また、研究者のフルネームを入れれば、 直接その人のホームページにたどり着けることもあり、かなりの情報収集を行っ ているな、という気がします。 しかし、とにかく強力すぎてしまって、 有用な情報をピックアップするのがかなり大変、という印象をもちました。 まだまだ修行不足を感じております。
なお、今回紹介した各サイトへのリンクは、 私のホームページからたどることができます。みなさんもご利用下さい。 また、何か役にたつサイトがあったら教えて下さい。
|
Last modified: Sat Oct 9 23:05:17 JST 2004
by R.Uehara (uehara@jaist.ac.jp) |
|