解けたら賞金1億円！　数学の7つの未解決問題のひとつ「P≠NP」問題へのアプローチがもたらすもの

P≠NP問題、進捗どうですか？

岡本吉央氏：よろしくお願いします。電気通信大学の岡本です。アルゴリズム分野の話をしたいんですが、なぜかP≠NP問題の話を今日はしようと思います。「みなさん、進捗どうですか？」というのがこの祭りのテーマなので、「P≠NP問題、進捗どうですか？」ということを話したいんですが、このP≠NP問題というのは、すごく大きな未解決問題なんです。

いろんなところで、これは未解決だと言われているんですけれども、これが今どのぐらい解決に向かって進んでいるのかということをお話ししたいと思います。私自身は計算幾何学とかグラスアルゴリズムとか、グラフドローイングと呼ばれている、グラフ描画ですね。グラフをいかに平面上、あるいは空間に描くのか。あるいは、最適化とかゲーム理論というものをメインに研究をしているんですけども、P≠NP問題っていうものに焦点を絞って話をさせていただこうかと思いました。

P≠NP問題っていう言葉を聞いたことある人はどれくらいいますか？　多いですね。どういう問題であるかっていうことを正確に言えるという人は、どれぐらいいますか？　自信はないですね。この話の中でも定義はしません。これを正確にやろうとするとすごく時間がかかってしまって時間が足りなくなってしまうので、それはちょっとお茶を濁すんですけれども。

P≠NP問題についてどのようなことが、今、考えられているのかという話をします。P≠NPというのは、簡単に言うと、PがNPと等しいのか、PがNPと等しくないのか。「どちらが正しいでしょうか」という問題です。

こう聞くと簡単な問題のように思うわけですが、これでは何も言ってなくて、PとNPってなんなんでしょうかっていう話になるわけです。

P≠NP問題は、ミレニアム懸賞問題の1つ

P≠NP問題というのは2000年に、多分カナダだったと思うんですけど、クレイ数学研究所というところが20世紀が終わるときにミレニアム懸賞問題という、いくつかの数学の未解決問題に対して懸賞金を出すといって大きく話題になったいくつかの問題のうちの1つの問題です。

そういう意味では、P≠NP問題という問題は数学の問題でもあるんですけれども、一方で情報処理の問題でもあるという、そういう特別な位置づけを持っている問題です。

今、ここに7個の問題が書かれているんですけれども、ポアンカレ予想だけは解決されていますが、他の問題はまだ解決されていない。未解決の問題です。ヒルベルトという数学者がいまして、19世紀の終わりにICMという国際数学者会議で、たくさんの未解決問題を出したんですけど、そのヒルベルトの出した未解決問題の多くは実は計算に関する問題だったという背景があります。

そういう意味でいうと実は、ナヴィエ・ストークス方程式の問題とか他の問題も計算に関係しているんですが、特に計算に深く関わっているのがP≠NP問題になっています。

PがNPと等しいのか、PがNPと等しくないのか、この2つのうちどちらが正しいのかというのがP≠NP問題なわけですが、簡単に言ってしまうと、Pというのは簡単な問題です。NPというのは難しそうな問題。先ほども言いましたように、正確な定義とかを避けて通りますので雰囲気で理解して下さいね。NPは難しそうな問題と思われているもので、この2つが同じか、違うかというものを問うているのがP≠NP問題です。

P≠NP問題とは？

1つの例ですけども、ここにグラフがあります。無向グラフですね。「ハミルトン閉路がありますか？」という問題です。ハミルトン閉路問題というのは、頂点をちょうど1度ずつ通って自分自身に戻って来る経路はありますかという問題です。

左のグラフ、これはハミルトン閉路を持っています。実際にこう書いてみると、あります。右のグラフはハミルトン閉路を持つでしょうか。まあ左は持つと言っているのだから、右は持たないのですけれども、どうやって右側がハミルトン閉路を持たないということを、皆さん確認しますか、といわれると、難しいですよね。

このハミルトン閉路問題というのはNP問題、つまり難しい問題と考えられている問題です。これによく似た問題があります。

オイラー閉路問題というものがありまして、オイラー閉路というのは先ほどのハミルトン閉路に似ているんですけれども、全ての辺をちょうど1度ずつ通って元に戻ってくることができますかという問題です。

例えば左のグラフにはオイラー閉路はあるんですけれども、じゃあ右のグラフにオイラー閉路はありますか。左があると言っているんだから多分右はないんですけれども、これはないですよね。

実は、オイラー閉路問題というのはP問題。簡単な問題だということが知られています。

これは、グラフとかグラフ理論、グラフアルゴリズムの授業を取ると、もしかしたらなんでこれが簡単にわかるかというのを聞いたことがある人もいるかもしれませんが、簡単な問題なんです。

P≠NP問題と言っているのは、このハミルトン閉路問題とオイラー閉路問題といっているのが「同じぐらい難しいですか、それとも同じぐらい簡単なんですか？」ということを問うている問題です。

先ほど、オイラー閉路問題は簡単だといったんですけれども、簡単と言っている意味はある意味で多項式時間アルゴリズムを持つという形で定式化されるんです。それで「ハミルトン閉路問題というのも多項式時間アルゴリズムを持つんですか？」ということがキーポイントです。

計算の本質？

なんで、このP≠NP問題というのが重要な問題だと考えられているのか。例えば、「『フカシギの数え方』、おねえさんといっしょ、みんなでかぞえて」という動画がありまして。

これは、この図にあるような、こういう格子状のグラフにおいてSからGですね、左上から右下に至る経路が何個ありますか、というのを数える問題というのが、どれぐらい難しくて、アルゴリズムを工夫するとこれが一瞬に解けるんだということを、すごくエキセントリックな方法で教えてくれるんです。

この問題は難しい問題だと考えられているんですけれども、こういういいアルゴリズムがないと思われている問題に対して、「本当によいアルゴリズムがないのか、それとも実はあるのか」というのを問うているのがP≠NP問題のようなものになっています。

これは数え上げ問題を対象にしているのでちょっと違うんですけれども、そういうフレーバーを持っているのがP≠NP問題です。つまり、計算の本質っていうのがどこら辺にあるのかっていうことを突き詰めたいっていうことがP≠NP問題の背景にあるわけです。そういう意味で非常に重要な問題です。

難しいと思われている問題が簡単だったら、社会が大きく変わる

重要であるという例もう1つです。これは1カ月ぐらい前に、皆さん覚えているかどうかわからないですけれども、東日本大震災の余震と呼ばれる地震がありました。余震があって津波注意報が出たんですけれども、そのあとで、また別のニュースが出てきて「実は津波注意報を出すべき範囲が間違っていました」と。

予想到達時刻、到達予想時刻も間違っていて、「そのときにアナウンスした時刻よりも10分早く到着することになっていました」ということを、あとで気象庁が発表したわけです。

これを読みますと、「気象庁によりますと、現在の震源を特定する手法では、津波注意報を出すか判断するまでの数分間で詳細な分析を行うことは難しいということで対応を検討した」としています。

この「数分間で詳細な分析を行うことは難しい」といっていることが計算の時間に関わる問題なわけです。なので、もしP=NP、難しいと思われている問題が簡単であるならば、数分で詳細の分析が難しいという前提が崩れますので、社会が大きく変わるわけです。

そういう意味で、このPとNP、同じか違うかということは社会に対して大きなインパクトを持っています。そういう意味でもすごく重要な問題であるというふうに考えています。

最近、『P≠NP予想とはなんだろう』という日本語訳の本が出版されまして、著者は右に出ているランス・フォートナウというアメリカの研究者が書いたんですけれども、この中の第2章に「P=NPであったら、どれほど世界は素晴らしいものになるんだろう」ということが書いてあって私も読んでいて、これは信じられないと思うんです。けれども、そういう世界が広がっているという意味ですごく重要なことであるということを、どの研究者も思っております。

100人の研究者に「P≠NP」が正しいかどうかを聞いてみた

では、この問題、P≠NP問題、これは、1970年代にクックとレヴィンという研究者が定式化したと言われていまして、その重要性はカープによって広く知れ渡るようになったんですが、ちなみにカープという研究者は、京都賞を何年か前に受賞して、ちょうどこのホテルの近くにある国際会館で京都賞の受賞記念講演がありまして、私もその講演会を聞きに来たんですけれども、すごくたくさんの人がいたなという思い出があります。

70年代に定式化されまして、いまだに解決していないというわけです。PとNP、等しいのか等しくないのか。2002年に、ガサーチという研究者が計算量理論の専門家100人にメールを送って「どっちが正しいと思いますか？」というアンケートを取りました。

多くの研究者はP=NPだと思ったのか、P≠NPだと思ったのか、というわけですね。専門家はどう思ったのかというと、100人中22人は、無回答。多分わからないという回答を出しました。

それで22人をのぞいた、78人中、イコールかノットイコールか。どれぐらいの人が答えたかと言うと、イコールの回答が9人。ノットイコールと書いた人が61人いました。その他というのが8人いますけれども、その他については、ここでは述べないことにしますね。

大方の研究者、専門家はノットイコールらしいと思っているんですけども、無視できない数の人がイコールと思っているわけです。無視できない数の専門家の9人がイコールと思っている。

これは2002年なので、今、この9人の人々がどう思っているかわかりません。それに無回答、わからない、意見の表明を放棄している人も22人いますから、どちらが正しいのかということに対して大きなコンセンサスが分野においてあるわけではないとも言えますし、61人がノットイコールと言っているんだから、ノットイコールが正しいと多くの人が思っていると言ってもいいですし、ちょっと微妙なところですね。

P≠NP問題の解決には、ほど遠い

それほど研究者が頭を抱えていまして、このアンケートでも、もしP≠NP問題が解決するときにイコールとして解決するんだったら、すごく短い間に解決するんだろうと思ってる人もたくさんいます。一方、ノットイコールが真実であって、これが最終的に証明されるには長い時間がかかるであろうと人々は思っています。そういう現状ですね。

さて「70年代に定式化されて解決が未来のある地点にあるとすると、どれぐらいこの問題に対する解決、進捗状況、進んでいるでしょうか？」と。

私、個人の意見ですけれども、「解決にはほど遠い」と思います。しかし、このちょっとの差に対して、人々はすごく大きな努力を払っているわけです。「このちょっとの隙間をつくるのに人々は大きな努力を払っていて、このちょっとの努力を積み重ねないと、おそらく解決には至らないでしょう」と言うわけです。

これは大変な道のりなわけです。だけども大変な道のりを一歩一歩、歩んでいかないとおそらく解決は得られません。じゃあ、こんな小さな隙間の間に、何があるのかと言うと、2つアプローチがあるわけです。

人々はP=NPを証明しようとするか、P≠NPを証明するかどちらかなわけです。どちらを信じるかによって、証明しようというアプローチが変わってきます。P=NPであることを証明しようとするんだったら、難しい問題に対して、すごいアルゴリズムをつくればいいわけです。

例えば皆さん、授業でアルゴリズムの設計技法とかいろいろ習っていると思うんですが、そういうのを駆使して、なんとかしてアルゴリズムをつくるということをして、難しい問題に対するアルゴリズムをつくることができれば、おしまいです。

あるいはP≠NPであると証明しようと思うんだったら、PとNP以外の様々な計算量クラスというのが知られています。そして計算量クラスというのが違うというような、証明がいろんな技法によってされてきています。

そういう技法を適用することによってPとNPも分離できるんじゃないかと期待するということを頑張って突き詰めれば「PとNPが違うんだ」ということを証明できるかもしれないというアプローチがあります。

問題への3つのアプローチ法

この流れで研究者は頑張ってきています。しかし残念ながら、今までの状況ではうまくいかない。なので、この問題のアプローチは3つあります。その内の2つは、このアルゴリズム設計技法、あるいは計算量クラスの分離技法を開発して、アタックすることです。

でもなかなか新しいアルゴリズム設計技法っていうのは生まれません。すごく難しいんです。じゃあ、他にもう1つやっていることは何かっていうと、うまくいかない理由を突き詰めようというわけです。できないんだったら、それは理由があるはずだと思うわけです。

その理由を突き詰めたいというところから、うまくいかない理由がわかると、またそこからアルゴリズム設計技法や、計算量クラス分離技法が新しく生まれてくるかもしれないというわけです。そこを突き詰めたいわけです。

分離に関する研究のフロンティア

この2つについて、例をあげて最近の研究のフロンティアを紹介したいと思います。まず、P≠NPを証明しようという方向ですね。これは、先ほど言ったように計算量クラスを分離したいというモチベーションなので、他のそういう結果を見て、その証明技法が使えないかということを考えます。

例えば、PとEXPTIMEというクラスがあるんですけれども、それが違うということが知られています。これは、計算量理論の講義をしっかりとやると、時間階層定理と呼ばれるものから簡単に出てくるんですが、証明された1965年、私も生まれていない、皆さんも生まれていない、そんなころから知られています．

「このPとEXPTIMEを分離するための証明技法を使って、PとNPを分離できますか？」と聞かれると、実は、多分できないと思われています。それは研究者が「相対化のバリア」と呼んでいるんですけれども、そういう証明法を使っても「相対化のバリア」というものがあって、うまくいかないということが知られています。これを言いだすとまたややこしいので、ちょっとお茶を濁しますけれども、こういうバリアがあるというのは重要で、このPとEXPTIMEを分離するときに使っている証明法では、PとNPは分離できないというふうに証明されています。

そうすると、別の分離法を持ってくるわけですね。また、20年ぐらい経ったときに、このAC⁰とNC¹。これも説明していると、また時間がかかるんですが、これは回路計算量理論のクラスなんですけれども、この2つは分離されている。この証明法をつきつめて、「これを使って証明できますか？」「PとNPを分離できますか？」と考える。でも、やっぱりできないということが、これはラズボロフとルディッチによって証明されました。

これは「自然の証明」というバリアが存在するということを彼らが言って、このAC⁰とNC¹を分離するような証明法では、PとNPが違うことを証明できなそうだっていうことを証明しました。

そのあと、ヴィノドチャンドランという人が、またある新しい証明技法を使って、あるクラスを分離したんですけれども、これに対してもアーロンソンとウィグダーソンが代数化というバリアがあるということを発見して、やっぱりこの証明もPとNPを分離するのに使えないことを証明しました。

最近、これは2014年、ライアン・ウィリアムズという若い人が、NEXPとACC⁰が違うものだというふうに、NEXPはACC⁰に含まれないっていう分離を証明しました。

これに対してバリアがあると思われているんですけれど、実はこの部分が、今、未解決です。このNEXPとACC⁰を分離する証明技法、もしかしたら、これを使えばPとNP分離できるのかもしれません。

だけどもわからない。もしかしたら、表の上の3つのように、ここにもなんかバリアがあるかもしれませんけれども、誰もそのバリアをみつけていないという状況です。ただしフロンティアとしては、このウィリアムズの証明技法というのは、PとNPを分離するための最後の一投となるのか、それともまた他の、前までの研究と同じようにバリアがあって、彼の証明法も使えないのか。

この2つは分かれ道、われわれも分岐点に立っているのですけれども、これが今、分離に関しては研究のフロンティアになっています。なので、計算量理論の人々は、このウィリアムズの結果というのを、じーっと眺めて、ここに書かれている証明テクニック、これって何なんだろうっていうことを深く理解しようとしているというのが現状です。

数理計画法や最適化理論を使ったアルゴリズム設計技法

今、話したのは右側のほうでした。じゃあ、この左側のほうですね。このアルゴリズム設計技法をうまく使ってP=NPを示したいんだけれども、うまくいかない。「なんででしょう」という話のほうのフロンティアを1つ話したいと思います。

一般的なアルゴリズム設計技法というのはあんまりなくて、ここに5つ挙げていますけども、私自身がこの数理計画法に深く馴染んでいるので、この数理計画法あるいは最適化理論を使ったアルゴリズム設計技法について、今からお話したいと思います。

この数理計画法に基づくアルゴリズム設計技法においては、何を行うかというと、元々何か問題が、NP問題が与えられるわけですが、それをまず整数計画問題に変換します。そのあとに続くのが緩和とか強化、こういう1つのステップを踏みます。

そうすると整数計画問題といわれていたものが凸計画問題に変わります。凸計画問題といわれている問題が、実は簡単に解ける問題なんです。そこで解いた答をうまく元の問題において解釈することによって、元の問題を解こうという枠組みが数理計画法によるアルゴリズム設計です。

今、難しいNP問題、特にNP完全問題と呼ばれているものがあるんですけれども、それがコンパクトな凸問題に帰着されるとすると、この瞬間にP=NPが言えます。これはすごいいいことなので、これを目指すわけです。

P=NPを証明しようと思うときには。ここでいっている凸計画問題といわれているものとしてよく表れるものは、線形計画問題、LPと呼ばれる問題です。またそれを一般化して現れる半正定値計画問題と呼ばれる問題もあります。

問題の表現力としては、半正定値計画が線形計画よりも強いというのが知られています。難しいNP問題を、コンパクトな線形計画問題、あるいは半正定値計画問題に帰着できれば、P=NPと証明できます。

実際に、ハミルトン閉路問題という問題は、NP完全問題になっています。ハミルトン閉路問題がコンパクトな線形計画問題、あるいは半正定値計画問題に帰着されればよいわけです。

「証明できないこと」を証明する

実際に80年代後半に、シュワートという研究者がハミルトン閉路問題は、コンパクトな線形計画問題に帰着できるというふうに書きました。これは間違っているんですね。つまりちゃんと定式化ができていないわけです。「人々は間違っていますよ」ということを指摘するわけです。

そうするとまた新しい定式化、帰着を持ってくる。また間違っていますよと言われると、また持ってくる。らちが明かないわけですね。なので、どうしましょう。ここでヤナカキスという人は、非負行列分解という道具を使うと「どう頑張ってもコンパクトな線形計画問題は、得られませんよ」っていう道筋を提案しました。これは1991年の論文に書いてあります。

そののち、2012年にフィオリニら、5人の研究者がこの非負行列分解を使う手法によって、ダメだと言えましたと、ようやくこのらちの明かないレースに終止符を打ったわけです。もっとちゃんと言うとハミルトン閉路問題はコンパクトな線形計画問題に帰着できないっていうことを彼らは証明しました。

これで一件落着と思いきや、まだわれわれには線形計画問題よりも表現力の強い半正定値計画問題が待っているわけです。だけども、これも、今年6月に行われる理論計算機科学の会議でコンパクトな半正定値計画問題に帰着できないということが証明できたと発表されます。

だからこういう意味でハミルトン閉路問題というのは、数理計画法を使ったアプローチでは、アタックできないということがわかったということになります。このようにして一つひとつの問題に対して、この問題に対してはこの手法では解決できないということを順番にやっていくことによってこの問題の構造というのを深く理解していきたいというふうに考えているわけです。

「P≠NP」問題は全く異なる手法で解かれる可能性もある

P≠NP問題の進捗については、もっと話があるんですけれども、特にフロンティアとして2つの話だけを今日はご紹介しました。実は、P≠NP問題に対するアプローチというのは、いろんなものがあります。

先ほど、最適化理論からのアプローチというのをひとつ言ったんですけれども、その他にもこの中にあるかどうかわかりませんけれども皆さんの専門としている分野や、進化論とか統計力学とかそういうものに関係しているという話があったりして、すごくそういう意味では多彩なアプローチが必要であると考えられているのもP≠NP問題のおもしろさの1つになっています。

実際、ポアンカレ予想というのは、元々ポアンカレ予想を考えていたトポロジストが思っていた手法とは全く違う手法を使って解かれました。そういう意味でも、P≠NP問題というのがわれわれの考えている手法とは全く違う手法で解かれる可能性もあります。

でもわかりません。この手の話については先ほども紹介しました『P≠NP予想とはなんだろう』という本にわりと詳しく書いてあります。あるいは、最近、2013年の2月を最近と言うかどうかわかりませんけれども、2013年2月号と2009年12月号の『数学セミナー』にいろんな記事が載っていますので、ここら辺、見ていただくとどういう状況なのかというのもわかると思います。2013年のほうの号には私も記事を書いています。

また、今日は話さなかった、もう少し詳しい『計算複雑性にまつわる10の誤解』、計算複雑性はわりと1人で間違いやすいんですけれども、そういう部分であるとか、『2と3の違い』という記事も私のウェブページにあります。

『2と3の違い』というのは何かと言うと、皆さん、修論発表で、「この問題が解けました」と言って、誰か先生が質問して「別の似た問題だけども、これも解けますよね」とか聞かれて「はい、そうですね」と答えた瞬間に、皆さんの修論は、失格になると。

なぜかというと、ちょっと問題を変えただけでPだった問題がNP完全に変わるというのがよくあります。怖いですね。その点に十分気を付けてください。

限界の究明も研究の一部なんだ

さて、「P≠NP問題、進捗どうですか」ではなくて、「皆さん、進捗どうですか」というわけです。

先ほどのP≠NP問題の状況を見てみると、今皆さんのとっているアプローチというのが結実しないかもしれないという恐れがあるわけです。だけどもP≠NP問題の研究の流れで言うと、限界の解明も研究の一部なんだということがわかると思います。

だから皆さんも自分の修論に対して、もし皆さんがもっているアプローチがうまくいかなかったら、その限界を究明するということも、十分テーマとしてはありえるんじゃないかと思います。

今日の話、その部分を最後に締めにして終わりにしたいと思います。ありがとうございました。