idea
computation
計算量

計算量クラスに関する着想とか

ニュース

ついにABC問題に対する望月先生の取り組みが論文掲載されましたね。おめでとうございます。

ちなみに自分の論文は3ヶ月間 With Editor で止まっているのですが、彼のケースに比べるまでも無く、まだまだ長くかかるのではないかなと... orz

本記事について

さて、本記事は日曜数学 Advent Calendar 2017 の16日目として書いたものです。

実のところ、本記事用に書こうとしていたところについて、既に数学界隈の壁の中で書いてしまっていました。ということで、自分のこれまでの取り組みに関して書きたいと思います。

歴史

出会い

中学生だったか小学校高学年だったかのころ、ブルーバックスグラフ理論と出会い、ハミルトン閉路問題が難しいことを知りました。いえ、実際にはハミルトン問題ではなかったのかも知れませんが、グラフを対象とした問題には、一見簡単に見えるものが実は難しいということが往々にしてあるということだったかも知れません。ともかく、最初はパズル感覚で「何か解けるかも」と思ってしまった、傲慢な子供時代だったようです。

高校〜数年前まで

何か書くものがあれば、四六時中グラフを書いてました。どうにかしてうまく解けないかと思っていたのでしょう。世の中のほとんどすべての学者の方々は P $\neq$ NP を信じているなか、どうして解けると信じていたのか、実際のところわかりません。

詰まった

このころ、最大独立集合問題を対象に、定数項を大きくする方向で計算量の次数を削ることができるアルゴリズムを作ろうとトライしていました。

条件を細かく分けていくことで次数を下げる方向で取り組んでいたのですが、計算量の下げ幅に対して条件の増加率がどうしても大きくなってしまうことから、この方向での探索は破綻することが目に見えてきました。多項式アルゴリズムを目指す方向として、分割統治モデルに落とし込むという方法があります。これについては影響範囲を局所化することが実質的には不可能であることがわかりました。次に、メモ化手法についてやってみたのですが、メモ容量の増加分が多項式サイズにならないことが見えてきました。

このころ、通常取りうる方法では先にすすめないことがわかりましたが、だからといって P $\neq$ NP の軍門に下る気は無かったようです。

ターニングポイント

与えられたグラフをその結合部分が薄いところで切断する課題において、グラフのラプラシアン行列の固有値を用いる方法があります。そこからの類推で、「グラフの接続行列における固有値が使えるんじゃね」と思いました。

ここで、グラフ同型問題に着目しました。与えられた2つのグラフが同型かどうかを問う問題で、NP完全問題であるサブグラフ同型問題の特殊型です。実際には、同じ固有値を持つ同型でないグラフ(Cospectral Graphs)というのがあって、そのままでは使えません。

どういうときに固有値が同じでも異なるグラフになるのかを考えると、接続行列の対角化を行って比較したとき、固有ベクトルも必要になることから、この部分も同じになれば良いとなります。それでも単純に比較することができないため、グラフ頂点ラベルの交換を行う作用を持つ行列を導入することで、比較可能になるのではないか、となりました。ここから、接続行列の固有値が重解を持たない時、グラフ同型問題が多項式時間で解けることに到達できました。

次に、本命であるサブグラフ同型問題です。グラフ頂点ラベルの交換を行う作用を持つ行列をそのまま用いることができないことから、ライングラフへの変換をすることを思いつきました。さらに、2つのグラフにおける固有値と固有ベクトルの関係を明らかにすることで、条件付きでサブグラフ同型問題が多項式時間で解けることを示せることがわかりました。最後に、必要となる条件を2つのグラフに適当な重み付き稜線を加えていくことで実現できることがわかりました。(このあたりについての解説は後日書こうと思っています)

ジャーナル投稿

ということで、国際学会に投稿したところ、「(英語を直してフルペーパーにして)ACM or STOC or FOCS に出すべし」と言われ、2017/09/26 にACM Transactions on Computation Theoryに投稿しちゃいました。未だに With Editor です。(これについては、とある先生から、結果が結果なので査読してくれる方が見つからないだろうとの意見を頂きました)

そして現在

その後、研究会や勉強会でお披露目して、研究者舐めるなとか言われたりもしていますが、めげずに生きてます ^_^;

まとめ

最初、私の P vs NP 問題との付き合いは細く長いものでした。最近になって、線形代数的に解く方法を見つけることができました。この学問領域を専門に研究している方々から無視や責められたりもされますが、このことについて、ちゃんと共有できるようになりたいと、日々思っております。