コンピュテーション研究会

研究会・学会

仙台です．今回のメインイベント (?) は「集中討論：DeolalikarのP≠NP論文をめぐって」です．電通大の垂井先生に騒動の顛末から少々テクニカルなところまで踏み込んで話がありました．スライドは垂井先生のページから (今は) 入手できます．

以下，今回の議論の私的まとめです．

  • Deolalikar (以下D) 論文が専門家に注目された理由とおぼしきもの：Liptonがブログで取り上げた．Cookが「It looks like a serious effort」といった．TaoやGowersが真剣に考え出した．
  • D論文がserious effortに見えた理由とおぼしきもの：統計物理，充足可能性問題，確率分布の複雑さといった広い分野の概念に記述が渡っていた (つまり，新しい方法論に見えた)．それでいて，Mulmuleyの枠組の流れに沿っているように見えた．論文自体が読めそうに見えた．
  • 8月中旬に「証明を与えていない」という結論が見えてきて議論は収束，ICM (International Congress of Mathematicians) が8月下旬に始まり，人々の関心はそちらに移行．
  • 専門家はすべて注目したのか？：そうでもないよう．
  • 何がいけないのか：LemmaやClaimがない．そのため，間違いをピンポイントで指摘することが困難．長すぎる前置き．
  • AKS「PRIMES in P」もプレプリントがweb上に出てきて，人々が議論をしだし，正しいという結論になった．今回と何が違うのか：そもそもAKSは正しかった．LemmaやClaimがある．短い．理解することが比較的容易．
  • D論文は相対化，Natural proof，代数化といったバリアを超えているのか？：それ以前の問題．
  • D論文を理解するためにTaoが定義したppとpppはPとどう関係してるのか？：ppではPを考えるのに弱すぎる．pppはP-samplableに近そう (同じ？ サポートが同じ分布を作れるというところまでは言えてそう)．
  • TaoがD論文は間違っていると結論付けた根拠とおぼしきもの：Dがppとpppを混同している．
  • 最近Mulmuleyの枠組を理解しようとする動きが広まっている．なぜか？：上記バリアを超えようとしている．理解することが比較的困難．

参加されていた方々，間違いなどがありましたらコメントをお願いします．