P≠NP問題とはなにか？【Wathematica Advent Calendar 2021】

Wathematica Advent Calendarの12/7の記事です。

現代の数学はとても広範で深遠な発展を遂げています。しかしそれでも、いまだに証明・反証がなされていない「未解決問題」というものが数多くあります。

例えばかの有名なフェルマーの最終定理はつい25年前までは未解決問題でした。つまり、それまではフェルマーの最終定理が本当に成り立つのか、あるいは成り立たないような反例があるのか、誰もわからなかった。

ABC予想の解決もそうですね。京大の望月教授が解決したということで、去年か一昨年に大きな話題になったと思います。あの命題も望月教授の論文が受理されるまでは「未解決問題」であり、だから名前も「ABC"予想"」だったわけです。

この2つの例はすでに解決されてしまった例ですが、今回紹介するのはいまだに未解決であるうちの一つの問題、「P≠NP問題」です。

P≠NP問題とは?
P≠NP問題の行く先
ミレニアム懸賞問題
おまけ
参考資料

P≠NP問題とは?

P≠NP問題とは、簡単に言うとアルゴリズムの「計算量」に関する問題です。計算量と聞いてぱっと来ない人も多いと思うので、例を挙げておきましょう。

計算量について

<例>(足し算問題) 正の整数 $n$ に対して、 $1+2+\cdots+n$ を求めたい。この計算はどれくらいの計算量で行えるか？

(「1回の計算」とは、2つの数の加減乗除を行うことを指すものとする)

この問題文に書いてある計算を実行する方法はいろいろあります。一番単純な方法としては、

(Step 1) $1+2$ を計算する

(Step 2) 上で求めた数に $3$ を足す

(Step 3) 上で求めた数に $4$ を足す

…………

(Step n-1) 上で求めた数に $n$ を足す

という方法がありますね。この場合の計算回数は $(n-1)$ 回となります。

つまり、この問題は高々 $(n-1)$ 回の計算を行えば解ける、ということです。このとき、この問題は計算量 $O(n-1)$ で解けるといいます。

$n \rightarrow \infty$ としたときは $n$ も $n-1$ も発散速度は変わらないので、通常は $O(n-1)$ ではなく $O(n)$ と書くことが多いです。ちなみに $O(n)$ は「おーだーえぬ」と読みます。

実はこの「足し算問題」は、ほかの解き方をすることもできます。数学Bあたりで習うと思いますが、

$1+2+\cdots+n=\frac{n(n+1)}{2}$

という公式がありましたね。これを使うと、次のように計算ができます:

(Step 1) $n+1$ を計算

(Step 2) $n \times (n+1)$ を計算

(Step 3) (1)で求めた数を2で割る

なんと、3回で計算が終わってしまいます！ここで大事なのは「どんな $n$ に対しても」3回で計算が終わるということです。と、いうことでこの問題は計算量 $O(3)$ で解けます。3も1も発散速度が変わらない(発散しない)ので、通常は $O(1)$ と書きます。

ちなみに、実際はどんな $n$ に対しても計算時間が同じ、というわけではありません。人間にとってはもちろん、コンピューターにとっても、 $1+2+\cdots+100000000000000$ を計算する方が $1+2+3$ を計算するよりも(機械はほんの少しだけ)大変です。

その理由は「『1回の計算』とは、2つの数の加減乗除を行うことを指すものとする」というところにあります。でも実際は、例えば5桁の数同士を足し算するときはまず一の位同士を足して、次に十の位を足して、...、というように5回の計算をしていますよね。このように「桁数」を考慮していないので、一見奇妙な結果が生まれるわけです。でも大まかなイメージはつかめていただけたかと。

P問題

ここからはいろいろな「計算問題」を分類していきます。

あるkがあり、計算量 $O(n^{k})$ で解けるような問題を「多項式時間で解ける」問題、または「P問題」といいます。例えば、さっきの足し算問題はP問題です。なぜかというと、方法1を使えばこの問題は $O(n)=O(n^{1})$ で解けるからです。ちなみにPは英語でPolynomial(多項式)のことです。

もしある問題が計算量 $O(n^{999})$ では解けなくても、計算量 $O(n^{1000})$ で解けたらP問題になります。

多項式時間での計算は、(例えそれが $O(n^{1000})$ であっても)「速い」計算とみなされます。では逆に「遅い」計算とは何か？例えば計算量が $O(n!)$ や $O(2^{n})$ 必要な計算です。 $n=1,2,3,...$ といった小さい数では $n!$ や $2^{n}$ は $n^{1000}$ に比べて圧倒的に小さな数ですが、nが大きくなっていくと最終的には前者の方がずっと大きな数になってしまいます。(これは、 $\frac{2^{n}}{n^{1000}} \rightarrow \infty \, (n \rightarrow \infty)$ であることからわかります。