P≠NPなのか－7つのミレニアム問題の１つの難問－

P、NP問題

ちょっと何を言っているのか分からないかもしれませんが、これもちゃんとした数学の問題です。しかも今でも未解決問題で、２１世紀になった２０００年にアメリカのクレイ数学研究所が、21世紀に解決すべき問題としてあげた７つの問題の１つです。これらには、賞金がかかっていて、解いた人には、１00万ドル受賞できることになっています。

P,NP問題は、1971年にカナダのトロント大のスティーブン・クックが３０歳の若さで提案した問題です。

ＰとＮＰとは何か

ＰとＮＰはともに問題の集まりで、\(Ｐ \subset ＮＰ\)ですが、\(Ｐ＝ＮＰ\)かどうかは分かりません。この問題は、\(Ｐ＝ＮＰなのかＰ≠ＮＰ\)なのかどちらなのかを明確にしなさいと言う問題なのです。

ＰとＮＰは、略号で、計算をするときの手順を示しています。Ｐに含まれる問題は、問題の大きさが増えるにつれて、多項式的に増えることをあらわしています。Ｐは、多項式をあらわす、Polynomial　の頭文字です。
また、NPは、Nonderministic Polynominal の略です。

たとえば、「任意の自然数Nが、素数でない場合に、素因数分解する。」という問題については、２進数であらわしたときには、\(Ａ＝log2N\)がこの問題となり、多項式的に増加するとは、「ある自然数ｋがあって、Nが大きくなると、いつかは\(A^k＝(log2N)^k\)より小さくなる」と言う意味です。

ＮＰはＮではないと、言っているのではありません。ＮＰはＰの否定なのですが、否定するものは、Ｐではありません。ＮＰに入る問題も、問題を解く手順で大きさが増えるにつれて多項式的に手数が増える手順があるということです。しかし、このままでは、Ｐと同様ですが、その違いは問題を解く手順の性質の違いなのです。

Ｐに入る問題の手順では、決定性、ＮＰに入る問題では非決定性なのです。
決定性の手順は非決定性の手順の各ステップで、選択肢が１つになったタイプと考えられますから、ＰはＮＰに含まれます。

コンピューターは逐次的に命令を処理しています。これは、プログラムが決定的ということになります。ここの問題を解く手順はイギリスの数学者アラン・チューリングの考えた手順を考えます。これをアルゴリズムと言います。

因数分解の問題

ある数Ｎの素因数を求めるには、小さな素数２から割っていけばいいのですが、\(\sqrt{N}\)  以下の自然数で割っていけば十分です。
よって、素因数分解の計算量は、最悪でも\(\sqrt{N}\) の計算量で解けることになります。

計算量は、傾向として対数関数になると、対数的、指数関数になれば、指数的といいます。

因数分解と暗号の関係

合成数Nの大きさを考えますが、２進法で考えます。\(A＝log2N\)が、この問題の
大きさになります。
一方、計算量は、\(\sqrt{N}\)です。

\(N＝２^A\)ですから、\(\sqrt{N}＝(\sqrt{2})^A\)　となります。
従って、素因数分解問題では、素因数を求めるアルゴリズムは、指数関数的に増加する
ことになります。
従って、この方法をとる限り、判定する数が大きくなると、コンピューターで素因数を
求めることは、非現実的なものとなります。

Ｐに入る問題

問題の大きさが増えるにつれて最悪の場合の計算量は、多項式的に増えることに
なります。
ただし、決定的な手順がわかっている場合は、問題はＰに入ることになります。

素数問題がＰに属することの証明

２００２年には、ポアンカレ予想が、ロシアのぺリルマンによって証明されていますが、
この年に、３人のインドのコンピューター数学者によって、ついに素数問題は、Ｐに
属することが証明されました。アグラワル、カヤル、サクセナという３人です。

カヤル、サクセナは、アグラワルの生徒で、大学院時代の卒業研究で素数問題の
計算量をといてしまったのです。

インド恐るべしです。あの超天才数学者ラマヌジャンもインドの数学者ですし、
０を発見したインドは、数学の分野であなどれない国なのだと思います。