PとNP

河村 彰星(情報理工学系研究科コンピュータ科学専攻 助教)

西暦2000年5月,クレイ数学研究所は千年紀の幕開けにあたり未解決問題を7つ挙げて各100万ドルの賞金を懸けた。その筆頭を飾るのが計算量理論のP≠NP予想である。

n 人の者がおり,どの二人が親しいか書き並べたリストがある。三つの班に分けて各班内はどの二人も親しいようにしたい。この問に答えるには,各人を班に割当てる3n通りのそれぞれが条件を満すか調べ尽すという自明な方法があるが,手間が余りに厖大である。

もっと素早く班分けの有無を知る(そして有れば見出す)術はないか。 ここで「素早く」とは,入力の長さに関する多項式の程度の手間で済むことをさす(ここでは入力のリストの長さが n2 程であるから,n の多項式と言ってもよい)。 たとえば三つでなく二つの班に分けるのであれば,そのような方法はある(考えてみよ)。 このように入力長の多項式(polynomial)以内の時間で解き得る問題の全体を計算量理論ではPとよんでいる。 勿論厳密には「問題」「時間」などの言葉にはきちんと定義があるが,その詳細よりも重要なのは,それが実際に即した概念であり,Pは現実の計算機で素早く解ける問題におおむね一致するという事実である。

班が三つの場合,素早い判定法は知られていない。ただこの問題は,自ら班分けを見出すのは難しくとも,もし或る班分けを示されたら,それが条件を満すか確かめるのはたやすいという性質をもつ。 このように解を確かめることは多項式時間でできるという状況で解の存否を問う問題の全体をNPとよぶ。 解を自ら見出すことを要しないのだから,当然NPはPよりも真に多くの問題を含む―と考えられるが,その証明が得られていない。 これがP≠NP予想である。上述の三班分けの問題も,Pに属しないことが示せない。 まだ人類の知らない上手い解き方がある可能性を除けずにいるのである。

何かを上手く配置したり,効率の良い解決を求めたりする工学の問題の多くは,NPに属する。 そもそもあらゆる数学的探究が,適当な定式化のもとで,やはりNP問題である(数学における証明というものは,発見するのは難しいが,与えられれば原理的にはただちに確かめ得るものである)。 これらの本質的な難しさを問うP≠NP予想は,知的な営みすべてに関わる重大な課題といえる。

さて,P≠NPはそう簡単に示されそうにないが,周辺には実際上も理論上も興味深い豊かな研究の裾野が広がる。 たとえば厳密に解くのが難しい問題なら近似解を求めるのがひとつの手である。ところが或る種の問題は近似的にすら解けないことが分かっている。 このように計算量の研究では,優れた算法を見出すことと,そのような算法の非存在を示すこととの両面から,計算の本質に迫ろうとするのである。

筆者はこの計算量の理論を,実数を含む数値問題に応用する研究を行っている。 また計算量における乱択(ランダムネス)の役割の解明を目指す東工大,電通大との共同プロジェクトも進行中である。