P≠NP

| コメント(0) | トラックバック(0)

私が勤務している会社はIT企業で、そこの研究所の人と付き合うということは、情報処理科学の専門家と付き合うということである。で、ある程度親しくなった研究員に、情報処理の分野で最大の難問は何かと聞いてみた。すると、即答で、P≠NPだろうという。あれが解けたら一発でチューリング賞だよね、とも言う。

それに対して私はああやっぱりそうですか、と答えて、それ以上突っ込まなかった。突っ込まなかった理由は明らかで、P≠NPの意味をよく理解していなかったからである。突っ込んだら一発でボロが出る。

と思っていたら、数学セミナー12月号が「計算量の現在」の特集ということで、まさにP≠NPのことを解説している。こういうのを、渡りに船というのだろう。そこで、数学セミナー12月号の解説をベースにコメントしつつ、メモしてみる。

まず、Pとはなんぞやと問うと、それは、計算量が高々多項式レベルであらわされるアルゴリズムである、ということである。例えば、n個のリストにおいて、線形探索によりあるエントリを探すアルゴリズムの計算量は、O(n)であり、n個のリストをソートするアルゴリズムは、n・log(n)で、これはn2より小さいので、計算量は、O(n2)より小さいといえる。いずれにしても、これらの計算量は、高々多項式レベルであるので、Pである。それでは、O(n1000)みたいなアルゴリズムがあったとして、これは、計算機で計算する分には大変そうであるが、Pであることには変わりない。よって、計算量の理論というのは、実用というよりもむしろ、次第に理論的側面に傾く。

では、NPとは何ぞやというと、計算量を高々多項式レベルであらわすことができないアルゴリズムということで、典型的には、r>1として、O(rn)なるような場合である。 すなわち、(∃m∈N)nmがあったとして、これと、rn)とを比較すると、nを十分大きくとると、nm<rnになってしまう。言い換えると、指数は結局、多項式に勝ってしまうのである。よって、計算量を高々多項式レベルとしてあらわすことができない、すなわち、指数だと、計算量の爆発が速いといえる。計算量が高々多項式レベルでありさえすれば計算機で手に負えるというわけでもないので、手に負えるかどうかを分かれ目にすることはできないが、ともかく、P≠NPは、例えば、計算量が指数レベルのアルゴリズムで、それを高々多項式レベルに帰着させられないアルゴリズムが存在するという、とてもつつましやかな命題を述べているにすぎない。フェルマーの定理などと較べてもあまりにもおしとやかである。何がそんなに難しいのだろう。

では、NPアルゴリズムには、どんなものがあるのだろう。例えば、次のようなブール方程式を考える。A(B1,B2,...,Bn) = 1 A()は、B1,B2,...,Bnの多項式関数であるとする。すると、上記の式に解があるかどうかは、素朴には、B1,B2,...,Bnに、0と1を順番に入れ替えて代入してみるよりなく、その計算量は、最大で2nである。これが多項式レベルのアルゴリズムに帰着できることもあるかもしれないが、一般にそれが出来るとは限らないのではないか。

そして、P≠NPの予想の解決が一見簡単そうに見えてしまうのは、なにかNPアルゴリズムをもってきて、それがPアルゴリズムに帰着できないことを示せばいいという点にある。NPアルゴリズムには、ハミルトン閉路問題、ナップザック問題など無数にあって、その中で適当な問題が選べそうなものである。しかし、Pアルゴリズムに帰着できない、という証明はやはり難しいか。

そこで、多項式時間変換可能という概念が導入される。それは、問題の集合Qがあって、f(Q)→Pという関数fがあり、∀q∈Q and q = true ⇒そのときに限って f(q) = trueであり、fは多項式時間で計算できるとき、問題Qは、問題Pに多項式時間変換可能と呼ぶ。

一旦、多項式時間変換可能という概念が導入されると、あるNP問題があって、すべてのNP問題がそのNP問題に多項式時間変換可能であるとき、そのNP問題を、NP完全問題と呼ぶことにする。この定式化は、トロント大学のStephen Cookにより与えられた。すなわち、そのNP問題は、NP問題中のNP問題、すなわち、最も難しいNP問題である、という次第である。

そんなNP完全問題など見つかるのかと、誰だって怪訝に思うのだが、Richard Karpは、3SAT問題、ハミルトン閉路問題、ナップザック問題、グラフ彩色問題など、いろいろなNP問題がNP完全問題であることを示した。すると、P≠NPはもう証明されてしまっているのではないか、なぜ、P≠NPが未解決などと世間はまだ言うのだろうか。

例えば、アルゴリズムを合理化する方法として、動的計画法、分割統治法、近傍探索、量子計算などさまざまな技法が存在する。また、NP完全問題の1つである3SAT問題に対して、O(2n)を、O(1.32n)程度まで減らすことが研究成果として出ている。しかし、既存のどんな方法を使っても、多項式時間にはならない。そこではなにか画期的なアルゴリズム合理化方法が案出されて、NP完全問題の双対としての、アルゴリズム合理化完全方法というのがあらわれ、NP完全問題にアルゴリズム合理化完全方法を適用してもPにならなかった、ということが示されれば、初めてP≠NPが証明されるのだろうか。しかしそもそもが、アルゴリズム合理化完全方法を案出するのが、とてつもなく難しそうである。こうしてようやく、P≠NPという予想の困難さが浮き彫りにされる。

実は、P≠NPの予想には、数学基礎論的側面があって、多項式時間で計算可能な問題の集合Pと、指数時間で計算可能な問題の集合EXPとが異なることが、対角線論法を使って証明できる。あれれ、するとP≠NPの予想はここで既に否定的に解決されているのではと思われるが、問題はそれで終わらない。というのは、チューリング機械のような仮想的な計算機をもちいた相対化という概念では、集合論的あるいは数学基礎論的手法では、矛盾が生じてしまう。これを克服するため回路計算量の概念が導入され、功を奏するかに思われたところ、NOTゲートが使われると突然、P≠NPの証明が破綻することが分かった。次に考えられた算術化の技法も壁にぶつかった。このように次々に手法が破綻していく様は、ポアンカレ予想の場合とよく似ている。ここまでで分かったのは、「相対化されず」、「自然な証明でなく」、「代数化できない」手法が有望である、ということだそうである。ある計算機科学者は、数学の華、代数幾何学にその解決策を見出そうとするが、途はあまりに遠いそうである。もしかして、数論幾何とか、非可換幾何などもタッピングされるのだろうか。こうして、P≠NPの予想には、一向に解決策が見えないようである。

ともかくも、訳もわからずメモしていくうちに、P≠NPの予想の証明の大変さだけは微かに感じられてきた。いずれにしても、P≠NPは、フェルマーの定理、ポアンカレの定理、リーマン予想のどれと較べても、素人受けしないこと甚だしいのである。

トラックバック(0)

トラックバックURL: http://commutative.world.coocan.jp/mt/mt-tb.cgi/1628

コメントする

このブログ記事について

このページは、あやたろうが2010年1月 1日 07:59に書いたブログ記事です。

ひとつ前のブログ記事は「チャウシェスク」です。

次のブログ記事は「風邪の効用」です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。