もうそろそろ一つのことをしっかり考えた方がよいかと思われるけども，まだいろいろなことを考えながらふらふらしている．
5月は総じて低調だった気がする．
ただ，Spring Schoolはとても勉強になったので，それはプラスポイントだと思う．
今日もスライド作りが中心．
証明が丁寧になりすぎてるかもしれない．
もうそろそろはじめないといけないかと思って，スライド作り．
まずはアルゴ研のから．
日本語で作るのは骨が折れるので，すみませんが英語で作っています．
ただ，英語で作ったスライドを使って日本語で発表するっていうのが自分にどれくらい違和感があるのか分からないので，実際の発表は変な感じになっちゃうのかもしれないです．
arXiv.orgに「A polynomial time SAT algorithm」というのが出てて，読もうと思ったけども，何か読む気がなくなってしまいました．
というのはすごく読みにくいからです．
主張もよくわからないし．
そもそも，「3SATが多項式時間で解ければSATも多項式時間で解けることが知られているから，以後3SATを考えていく」っていうなら，タイトルは「A polynomial tie 3SAT algorithm」であるべきでしょう，といいたくなる．
なんか用語法も少し変だし，英語自体も変な感じがする．
ということで，P=NPはまだ解けていない，というのが僕の見解です．
(読まないでおいてそういうことを言ってしまうのはよくないことはわかっているのですが...。)
やはり結局，最小費用流問題というか，組合せ最適化が全然わかっていないことがわかった．
例えば，一つの問題に対していろいろアルゴリズムがあるわけだけども，それらの妥当性の関係がよくわかっていない．
僕の場合はだいたい多面体を見てるので，一番分かりやすいアルゴリズムは単体法になる．
単体法は基本的に多面体の辺を辿っていくだけだから．
最小費用流の場合はネットワーク単体法になる．
一方，負閉路消去っていうのは多面体にどうなってるのか，というのがよくわからない．
単体法でないのだから多面体の内部を通って最適解まで辿り着いていると思うのだけども，内点法みたいな数値計算ではなくて，もっと離散的な方法で内側を進んでいっていることになる．
というところで思い出したのが，石関さんのやっている最小費用流とグレブナ基底の話しで，テストセットみたいなのが負閉路消去に対応してて，残余ネットワーク自体はどんどん更新されていくから，そのテストセットみたいなものっていうのもどんどん更新されていく，というのが実は多面体的な(というか，格子点的な?)理解になるのかもしれない．
...って，こんな，研究のアイディアみたいなものをそのまま書いてしまっていいのだろうか．
ということで，遡って20日の出来事から順に書いてきます．
バスの中ではほとんど眠っていたのだけれども，ついてからすぐ夕食そして自己紹介，という感じでその日はそれで予定されたものはおしまい．
これでだいたい20:00は過ぎていたのだけれども，まだ外が明るいので，辺りを皆で散歩したりした．
ヨーロッパに来てから思うのは，こちらの人は会議とかワークショップのときの空いた時間に歩き回るのが好きだ，ということだ．
このChorin村も森と湖が到るところにあり，歩き回るには事欠かない．
ということで，1時間ぐらい歩き回って，その後少しビールを飲んでから寝た．
で，講義の方はと言うと，Lisaの話は難しかった．(ほとんど理解していないと思われる．)
ということで，演習もなかなかてこずった(というか，ほとんど解けていない)．
演習は4人ぐらいのグループで議論しながら問題を解く，というものなのだけども，全然貢献できなかったような気がする．
ということで，この日はちょっと低調だった．
ただ，動的フロー問題は面白い，と感じることは出来たし，time expanded networkやtemporally repeated flowといった基本的な概念はよく分かった．
多入力多出力の場合のHoppe-Tardosの論文も見て，もっと勉強した方がよいかな．
で，午後の方はスケジューリングの話だったのだけれどもほとんど沈没していた．
内容は面白いのだけども，早すぎてちょっと着いて行けなかった．
新しい概念がどんどんどんどん出てきて，それらの関係が掴めないまま先に進んでいってしまった．
もう少し質問したりしてとめればよかったかもしれない．
で，午後は遠足．
古い教会の遺跡があって，見に行きたい人が多かったらガイドをつけるけども，っていう話になったので，ひょこひょこついていくことにした．
で，行ってみたらガイドはドイツ語．
(まぁ，当たり前なのだけども．)
ということで，ガイドの人が喋った後で，ドイツ語が分かる人は分からない人に通訳をする，というなんか不思議な状況になっていた．
この教会の遺跡自体は，今では音楽会などが行なわれるスペースになっているようだ．
ということで，夕食後バスはベルリンへ．
ベルリンに着いたらすごい雨でしたけど，ベルリンでもう1泊して，次の日にチューリッヒに帰ってきました．
というか，少し劣モジュラを知っているからといって，そちらの考え方に流されているのかもしれない．
もっとも僕の周りの人は劣モジュラについてあまり知らないと思われるので，そこら辺の知識の共有ができればよいのだけども，まだそこまで自分がまとめきれていないのが現状．
集合関数のクラスがしっかりと与えられてしまっているのだから，pseudo-boolean functionsのところで言われてる枠組とか，協力ゲーム理論のところの概念だとか，使えるものはたくさんあるのに，何もかもがうまく行きそうに思えない，というのはいったいどういうことなのだろうか．
自分の研究がまだ深まっていないのだと信じて掘り進めていくしか仕方がない．
宝箱が埋まっていることは誰にも分からないのだから，信じるしかない．
ICMのサテライト会議に受理されたという「二度目の」メールが来た．
しかし，こういう受理通知が二度ともサーキュラーレターとして送られてくるのはいかがかと思う．
前回のは「Dear Participants」ではじまっていて，今回のは「Dear Mr. Yoshio Okamoto」ではじまっていた．
ICMのまわりで起こっている僕にとって不思議なことはこれに留まらないので，ICMに関わる全ての事柄がとても不安になっている．
ということで，今日の総括は「不安」ということのようです．
気分転換に，表紙に写真を貼りました．
去年のNACAのときに毛利さんに取ってもらったものです．
本来は隣にRockafeller先生と平林先生が写っているのですが，カットしました．
JCDCG2002の〆切が8月の半ばである，ということは，これに行こうと思うんだったら相当頑張らないといけない，ということか．
「一番の思い出はフリーセルを教えてもらったこと」というのはとても光栄です．
来週はベルリンでCGC Spring School on Approximation Algorithmsなんだけども，
もうこの秋のCGC Fall School on Algorithms for Hard Problemsの案内が来ている
こちらの方は，普通の近似アルゴリズムだけでなく，オンラインアルゴリズム，アルゴリズムの確率的解析，Parametrized Complexityなど，幅が広くなっている．
特に，Parametrized Complexityは最近少し勉強したことなので，とても興味深い．
こちらも参加することにしよう．
やはり計算幾何の基礎が足りないらしくて，というか計算幾何独自のデータ構造というのになかなか慣れない．
そのようにいろいろと新しいデータ構造を作ってどんどんと高速化できていくことはやっぱり面白いんだけども，なかなかその分野に入っていくのには大変そうだ．
取り敢えずは，いろいろと勉強しなきゃいかん，ということだな．
東京滞在はどのようにするのかいろいろ考えているけど，なかなかこれといったいいアイデアが出ない．
ホテルでは高すぎるのだけれども，かといって，ウィークリーマンションみたいなものも案外高い．
というか，航空券すらやばいかもしれない．
早く予約する必要がある．
更に，ICMサテライトのregistratin feeを払わなければならないが，
払い方がよくわからない．
いろいろ調べてわかったのは，この前にやったICM本体の参加費の振込はうまくいっていない可能性が高い，ということだ．
そもそもサイトに情報が不足している．
もっとも僕も銀行に口座を作ればもう少しスムーズに振込できるのかもしれないけれども，それにしてもどういうことなのだろう．
僕自身がドイツ語操れないのがまずいことなのかもしれない．
と，今日は全然研究していないこともわかったので，家に帰ってから論文でも読もうかな．
いきなり証明にかかったけども，やっぱり間違ってた．
でも，相談できる人がいるというのは嬉しい．
割と自分の持っている問題ごとに相談する人を替えたりもしていて，うまく環境を使えてるのではないかと勝手に悦んでる気がする．
以前書いたけども，crosspolytopeがextendably shellableかどうかが未解決なので，計算機でも回してちょっと試してみようと思ったけども，4次元で力尽きた．
そもそも，すべての部分複体を出力した時点で6万とかになっていて，「rm *.dat」とやってもファイルの数が多すぎて削除できませんとか言われてなかなか困ってしまった．
何かこの問題が未解決である，というのが分かる気がして来た．
僕としては，こういう研究ははじめはたくさん例を作って眺めてみるのが大事なのだけれども，組織的に全部見ようとか思うとやはり計算機を使うのがよい．
しかし，最近は計算機で列挙するというのもなかなか大変なんだな，ということが身をもって分かってきた．
今日読んだ論文で，EgeciogluとGonzalezの"A computationally intractable problem on simplicial complexes" (Computational Geometry: Theory and Applications 6 (1996) 85-98) というのはなかなか面白い．
2次元単体的複体の可縮性判定問題がNP完全であることを示すのだけれども，そのときにつくるgadgetが何かかわいい．
かわいい，とか書くと，「あぁ，とうとうこいつも逝ってしまったか」と思われるかもしれないけれども，NP完全性の証明などに出て来る込み入った構成法はたくさん見ている間にだんだんかわいく思えるものである．
はじめの頃は，変な構成法だ，と思っていたりしたのだけれども，最近はその構成法の中に隠れているもとの問題の構造とかそういうものが見えてくるようになって，楽しさが増しているのだと思う．
ちなみに，あぁ逝ってしまったか発言としては，「4次元が見える」とかそういう発言はやばいらしいです．
僕は割と4次元が見えるのでやばいかもしれないです．
ただ，4次元を絵に描くことはなかなか難しいですね．3次元でも難しいのに．
だいたいの場合は投影をするわけですけど，4次元の絵を描く時には2回投影しないといけないくて，うまく投影しないと元の構造が何もわからなくなってしまうので難しいです．
ただ，多面体の場合はうまい投影の仕方が開発されてるので，そこら辺は便利ですね．
Delaynay分割のプログラムは諦めた．
報われる感じがしなかったから．
本来はもっとよい方法があって，それでやるのが普通なのだから，今回のはパスすることにしよう．
Parametrized Complexityについてちょっとサーベイをした．
自分の今考えている問題に対して使えるかどうかはいまいちよくわからないけれども，知っておいたほうがよさそうな気もする概念．
最近はComputational Complexityの分野が面白そうに見える．
SAOPの案内が来ていたけども，この日程なら7月のSAOPは何とか行けそうだ．
楽しみ．
外出したついでに，Spring Schoolのための航空券を買いにいった．
国際学生証もつくってもらったのだけども，窓口の店員さんは東大の学生証を見て「うーん」と唸ったのだけども，なぜか作ってもらえた．
なかなか不思議である．
夕方にセミナー(というか特別レクチャーみたいなもの)があって，
Adi Shamirが暗号のことについてしゃべるのを聞きにいった．
暗号というと，代数幾何とか数論とか難しいイメージがあるのだけれども，徹頭徹尾組合せ論のはなしで終始していて，暗号にこういうアプローチもあるのだな，ということが知れてよかったと思う．
内容はCRYPTO2002にアクセプトされたもの，ということらしいので，いずれ目にすることができるだろう．
三角形分割をするプログラムを書いているのだけども，うまく行かない．
この筋では有名なhalf-edgeデータ構造というを使おうとしているのだけれども，いまいちうまくいかない．
このデータ構造を使わなかったら三角形分割はできるのだけども，これを使わないとDelaynay三角形分割まで話しが進まないので，どうしても使いたいのだけども，どうしてうまくいかないんだろうか．
そのcorefereeとしてGuenter Roteが来たので，セミナーで話しをしてもらうことになっていた．
セミナーでの話しはフレームワークのrigidityの話しで，細かい議論を省略して例を使って説明してもらえたので，割とわかりやすかった．
個人的にはもう少し代数的にやってもらえた方が嬉しかった気がする．
フレームワークのrigidityの問題はそれ自身がmotion planningへの応用があるだけでなくて，多面体の理論ではg-定理(縮退していない多面体の面の数の特徴づけを与える定理)を示すための基本的な道具としても使われるので，僕自身も興味があるが，今日の話しはインスパイアされた，というか，これは最小費用流問題なのでは?と思ったりもしたのだけども，質問するのを忘れてしまった．
牧野さんの2002/5/3ですが，大変参考になります．ありがとうございます．
こういう意見を見ると，ピアレビューをどうやって信用していいのか，っていうのがよくわからなくなってしまいます．
もっとも，件の論文はレビューであって，その筋の専門家の大御所が書いたのだと推測されるので(同じ号の単体法のところは最近映画でも有名なJohn Nashが書いている)，そのような致命的なところがいくつもあるというのは非常に驚いたわけです．
Thomasのところに行ってミーティングをして来た．
去年の終わりにプロジェクトでやったものを論文にしたい，と僕が変なことを言い出したためだ．
一応，この夏に日本のどこかで話すつもりなので，それまでにもう一度まとめなおす，といったところだ．
また，ミニ情報みたいなものなのですが，先月の終わりに書いた「トップ10」みたいなものですが，計算複雑性(Computational Complexity)の方で，L. Fortnowが1994年の終わりに「ここ10年の計算複雑性の定理で私のお気に入りトップ10」みたいなのを話していたようです．
上のリンクのTalkのところからそのときのスライドが見れると思います．
選んだのは1984年から1994年ということなので，少し古いのですが，僕はほとんど分からないので，これだけ見ても何のことだか全然わからないのですが，この前と同じように列挙してみたいと思いますが，今回は日本語訳がよく分からないので英文そのまま載せてみます．