今日の一言/2017-7-22

RS-RSB/easy-hard 対応

D3の高橋くんと卒業した高邉くんとの論文が出版された

http://journals.jps.jp/doi/abs/10.7566/JPSJ.86.073001

「この問題は簡単か難しいかを答えよ」

という問いは一般には難しい。「誰に聞いているの?」というのは至極まっとうな回答である。難しさの判断は大抵の場合解く人の主観であるから、誰がどのように答えるのかに依存する。そもそも、この問いに何かしらの普遍的な解は与えられるだろうか？

最初の美しい解答は計算理論によって与えらた。解を得るために必要な計算時間やメモリー量に注目しようというわけである。ここから解説し始めるとたっぷりな講義になってしまうので省略。

計算理論による困難さの基準は最悪評価に基づいている。典型的な難しさももちろん認識されているが、その解析や解析するための設定が難しい。もっとも単純な設定はランダムな問題群を定義して、その中での典型的な困難さを評価することである。それはランダム系の統計力学と数理構造は同じであり、そこに現れるレプリカ対称性の破れが典型的な計算困難さを表す概念になりうるのではないか？というのが、物理学者の大いなる妄想である。すなわち、

レプリカ対称性がある＝簡単 -> Replica Symmetry = easy
レプリカ対称性が破れる＝難しい -> Replica Symmetry Breaking = hard

である。これをRS-RSB/easy-hard対応と呼ぼう。

背景にはスピングラスの研究から「レプリカ対称性が破れると自由エネルギー地形がぐちゃぐちゃになって、それはそれは解くのが難しそうになっている．．．ことがあった」という数少ない経験則に基づいている。個人的にはこの安易な「描像」には慎重な立場であるが、ものすごくノリ気である。結構、本気なので慎重なのである。すでに最適化問題の対応関係には反例は知られているので、完璧に普遍的な世界があるわけではなく、何かしらの条件付けが必要である。どこまで広いクラスで対応関係が成り立つのだろうか？もう少し妄想を続けてみたいわけである。

今回は、最大独立集合とよばれるNP hardな問題に対して、典型評価を調べたところRS/RSBの転移と、近似解法であるLeaf Removal(LR)が正解を出す/出さない転移がずれているという先行研究に端をなす。近似解法が正解を出す状況はeasyで、出せなくなるのはhardだろうと考えると、その境界がRS/RSB転移とずれているのは、妄想を信じる我々としては大問題である。何か妄想を生き残される見落としがあるのではないかと検討したところ、そのずれの原因は元々のLRがショボいだけじゃないか？というのが高橋くんの指摘であって、ちょっと賢く動的計画法と組み合わせると、改良LRが多項式時間で正解を引いてくる限界がRS/RSBと一致することを見出した。また、一つ妄想が生き残ったという研究であった。

ちょっとだけ研究体制についてコメント：研究室の指導方針として、理論研究なのだから、学生さんは別々に好きなことをやってもらおうとしている。結果として、学生同士が共同研究の論文を書くことはないようにしてきた。これからもおそらくないと思う。ただ、この論文は、高橋くんと高邉くん（現名古屋工業大学）の禁断？の共著論文となったわけだが、高邉くんはもう卒業したからいいか。