問題の難しさのクラス P と NP

これまでに説明してきた問題は、効率的な解法が知られている問題ばかりであった。しかし世の中の問題がすべてそううまくゆくわけではない。なかには大変に難しいものもあり、また計算機では決して解けないということが証明できるものもある。問題の難しさを数学的に定式化することも行われているが、今回はそれをうんと簡単にして説明を加えたい。
問題を計算機で解く場合には、まず具体的な問題 (instance) を何らかの形で入力しなければならない。その入力に必要なビット数を N とする。このとき、ある多項式 P(x) に対して、計算量が O(P(N)) となるような、この問題を解くアルゴリズムが存在するとき、この問題はクラス P に属するという。これまでに扱ってきた問題に対しては O(N) とか、O(N log N) とかのアルゴリズムが存在するので、これらの問題はいずれもクラス P に属するものであった。

もう少し難しい問題のクラスとして、NP がある。ある問題とその答えが与えられた時に、その答えが正しいということを確認するのに必要な計算量が多項式オーダーとなる問題のクラスが NP である。NP の N は Nondeterministic（非決定性）の N なのであるが、それについての説明はここでは省略する。

あきらかに、例題のハミルトン閉路問題と巡回セールスマン問題は NP のクラスに属する。答えが与えられれば、それがちゃんと問題の解になっていることを確かめるのは簡単であるからである。また、クラス P の問題はすべて NP にも含まれている。

なお、NP 問題では与えられた問題に指定された解がない場合についての規定はない。与えられた問題に指定された解がないという判定を行う問題は、これらの問題の双対問題と呼ばれる。NP 問題の双対問題がつくる問題のクラスは co-NP と呼ばれている。

多項式時間帰着
さて、ハミルトン閉路問題と巡回セールスマン問題はどちらが難しいであろうか。そのような比較をするために、ある問題を別の問題に帰着させるということが行われる。
この場合、巡回セールスマン問題の方が難しいということが簡単にわかる。あるハミルトン閉路問題が与えられたとしよう。これから次のように巡回セールスマン問題を構成する。

都市の数はグラフの頂点の数と同じとし、i 番目の頂点と i 番目の都市とを対応させる。
グラフの頂点 i, j に対して i と j をむすぶ辺があれば都市 i, j 間のみちのりを 1, 辺がなければ 2 とおく。
巡回路の長さの限界 K は N とする。
すると、もしこの巡回セールスマン問題に解があれば、道のり 1 の都市間だけを通って N 個の都市を巡回したはずなので、もとのハミルトン閉路の問題を解いていることになる。
明らかに、与えられたハミルトン閉路の問題を巡回セールスマン問題に帰着させることも、巡回セールスマン問題の解をハミルトン閉路の解に読み直すことも、多項式オーダーの計算で済む。このように、ある問題を別の問題に読み替えて解くことを帰着といい、特に多項式オーダーの時間で帰着できるかどうかに注目する。

多項式時間で帰着できるため、もし巡回セールスマン問題が多項式オーダーの時間で解ければ、ハミルトン閉路の問題も多項式オーダーの時間で解けるということになる。この意味で、巡回セールスマン問題はハミルトン閉路問題よりも難しい（厳密には、易しくない）といえる。

NP 完全
この計算量と多項式帰着という枠組みで、すばらしいことが証明できる。なんと、すべての NP の問題は多項式時間で巡回セールスマン問題に帰着させることができるのである。このような性質を NP 完全性と呼んでいる。
実は、ハミルトン閉路問題も NP 完全な問題である。従って、巡回セールスマン問題も多項式時間でハミルトン問題に帰着させることができる（はずである）。これらの問題の他にも、百以上にも及ぶ NP 完全な問題が知られている。

ある問題が NP 完全であることがわかっているとき、それを多項式時間で別の NP の問題に帰着させることができれば、その問題もまた NP 完全である。これはそんなに難しくない。しかし、最初に何かの問題が NP 完全であるということを証明しなければならない。これは（予想通り）かなり長い証明を必要とする。

P ≠ NP ?
さて、上記の説明から、何か一つの NP 完全な問題に対して多項式時間で解けるアルゴリズムが見つかれば、すべての NP の問題は多項式時間で解けるということになる。すなわち、クラス NP がクラス P に一致することになる。しかし、百を越える NP 完全の問題のなかで、多項式時間で解けることがわかっているものは一つもない。
それでいて、NP に属するどの問題に対しても、多項式時間で解くアルゴリズムが存在しないことも証明されてはいない。従って、現在に至るまでクラス P とクラス NP が同じなのか違うのか、結論が出ていないのである。これは情報科学の基本問題のなかで最大の未解決問題である。

しかし、沢山の人が取り組んでも NP 完全な問題のどれひとつとして多項式時間で解けるアルゴリズムを見つけることができなかったということは、 P と NP が異なるという状況証拠ではある。現在では NP 完全な問題に対していつか多項式時間のアルゴリズムが見つかるということを期待している情報科学者は少ない。

NP 完全問題の解き方
現状では、NP 完全問題、あるいはそれ以上難しい問題については、「効率的な解法はありません」と言わざるを得ない。では、NP 完全問題にぶちあたったらさっさとあきらめるべきか、というと、そうではない。
次章以降では、時間がかかるのは覚悟の上で、とにかく解を求めるという方法、および、厳密な解は得られるとは限らないものの、解に近いものを求める方法について説明する予定である。