P≠NP予想に関するメモ

今夜のブログはだいぶ前に宣言してしまった数学の難問P≠NP予想についてのトリビアな日記です。なお、最初に申し上げておきますが、PはPolinomialの略で、NPはNon-Polinomialの略です。Polinomialとは多項式のことです。経済学でも分布ラグを取った推計を行う場合に多項式の知識が必要とされます。アーモンラグとか、シラーラグとかです。当然ですが、知らない人は知らないと思います。
詳しいことは後にしますが、PとNPの関係については、P⊆NPであることは容易に証明できます。というより、私のようなシロートが考えてもほぼ自明です。しかし、P＝NPであるか、P≠NPであるか、すなわち、どうしてもPでないNPが残ってしまうかどうかについては、私のようなシロートにも、直感的に、後者が正しくて、NPが残ってしまうんではないかと予想されますが、証明した人はいません。有名なクレイ数学研究所が出したミレニアム懸賞問題のひとつです。シロートの私から見ても、もっとも解決が困難な問題だろうと思っています。もっとも、私なんかから見れば、数学の問題なのか、ゲーデルが解いたので有名な不完全性定理のような論理学の問題なのか、よく分からないくらいです。

これで理解できれば苦労はないわけで、今夜のブログは終わってしまうんですが、もちろん、よく分からない向きも多かろうと思います。
Pとは多項式時間で解ける問題を指します。これでも十分よく分からないんですが、要するに、2次方程式の解の公式みたいに、一般的な解法が存在する問題です。それに対して、ご想像の通りなんですが、NPとは多項式時間では解けない問題を指します。要するに、一般的な解法がなくて、総当りでリカーシブにしか解けない問題です。例えば、素因数分解などです。常識的に考えても、P＝NPであることを証明するためには、現在及び将来にわたるすべてのNPがPであることを証明しなければなりませんが、P≠NPであることを証明するためには、たったひとつでもいいから絶対にPにならないNPを探し出せばいいことになります。要するに、P≠NPの証明の方がラクそうに見えます。でも、まだ何も証明されていません。
ですから、繰返しになりますが、P⊆NPであることはほぼ自明なんですが、P＝NPであるか、P≠NPであるかについては、よく分かりません。P＝NPであれば、考えられるすべての問題は一般的な解を求める公式みたいなのがあり、現時点で、リカーシブにしか解けない問題でも、将来的には一般的な公式が発見されるハズだということになります。逆に、P≠NPであれば、一般的な解を求める公式がある問題と総当りでリカーシブにしか解けない問題と、この世の中には2種類の問題がある、ということになります。ただし、注意すべきであるのは、このP≠NP予想はチューリング・マシンなどにおける計算アルゴリズムに関して持ち出されたりするんですが、一般的な解の公式が存在したとしても、リカーシブな総当りで解く解法より、必ずアルゴリズム的に簡素ですぐれているとは限らないことです。解の公式があったとしても、リカーシブに解く解法の方がアルゴリズム的にすぐれている場合も排除できないわけです。
例えば、いつかのブログに書いた通り、現時点では、一般的な微分方程式を解く解法はなく、わずかに、変数分離型の微分方程式などが解の公式に沿って解けるだけなんですが、もしも、P＝NPであれば、将来的に、変数分離型でないものも含めて、すべての微分方程式を解く一般的な解法が得られることになります。もちろん、いつのことになるかは分かりませんし、解の公式のアルゴリズムの方がリカーシブな解法より簡素ですぐれている保証はありません。
より具体的な例で申し上げると、円周率πを求める問題を考えます。円周率を求めるのはすでにいくつかの公式があります。三角関数のarctanの級数展開で求めるもの、ζ関数を用いて求めるもの、その他として、人名を冠したガウス・ルジャンドルの公式、ボールウェインの2次の収束の公式、同じく、ボールウェインの4次の収束の公式、BBPの公式などです。こういった公式のほかに、モンテカルロ式にリカーシブに求める方法もあります。(x, y)のそれぞれのxとyを(-1, 1)の開区間で乱数を発生させ、x²+y²が1より小さいか大きいかの分布を見ます。容易に想像できると思うんですが、1より大きいのと1より小さいのが発生する頻度の比率は4-π：πになります。円周率を求めるいくつかの公式をメンドウなもので記さなかったんですが、公式によってはモンテカルロ式にリカーシブに円周率を求めるアルゴリズムよりも、決して、より簡素ですぐれているとはいえない場合もあると考えられます。

私は数学者ではなくエコノミストですし、それなりに、BASICでプログラミングもしたりしますので、このP≠NP予想については大きな興味を持っているんですが、同時に、大きな疑問も持っています。何度か繰り返しましたのでお気づきでしょうが、P＝NPであることが証明され、すべての問題がPであって、一般的な解法が存在するとしても、たとえそうだったとしても、一般的な解の公式に沿ったアルゴリズムで解くよりも、NP的でリカーシブなアルゴリズムで解く方が簡素ですぐれている可能性が排除されないからです。ですから、むしろ、焦点は、PならざるNPの問題が存在するのかどうかではなく、Pである問題の解法のアルゴリズムはNPよりも常に簡素ですぐれているのか、が、実用的・実践的に重要だと思うわけです。
というようなことを、我が同業者のエコノミストに最近質問してみました。つまり、多項式時間で解けない問題があるかどうかではなく、問題の解法において多項式的な解き方のアルゴリズムはそうでないアルゴリズムよりも常に簡素ですぐれているか、が実践的に重要ではないか、また、多項式時間ではなく、実際の生活時間で短い時間で解ける方が実用的なんじゃないの、と質しました。私は京都大学経済学部出身ですが、その人は東京大学理学部数学科のご卒業です。数学的な素養は私より格段にすぐれていると考えられます。私がこのようにアルゴリズム的・生活時間的な実用性の観点からのお話をすると、一言、「何で実用的じゃなきゃならないの？」と聞き返されました。私は再反論することが出来ませんでした。

やっぱり、経済学的なアタマと数学的なアタマは違うのかもしれません。
今夜のブログはP≠NP予想に関するトリビアな日記でした。