P対NP問題とは：定義・歴史・重要性（コンピュータ科学のミレニアム賞問題）

明確化

例えば、何か問題を抱えていて、誰かが「あなたの問題の答えは、1、2、3、4、5という数字の集合です」と言った場合、コンピュータはその答えが正しいか間違っているかをすぐに判断できるかもしれませんが、実際にコンピュータが「1、2、3、4、5」を自力で考え出すには、非常に長い時間がかかるでしょう。また、素数の発見もその一つです。素数であるかどうかを調べるのは簡単ですが、そもそも素数を見つけるのはとても難しいことです。この種の興味深い実用的な問題では、答えをすぐに見つける方法がありませんが、答えが与えられれば、その答えをすぐにチェックする、つまり検証することができます。このように、NP問題は「なぞなぞ」のようなものだと考えることができます。「なぞなぞ」の答えを出すのは難しいかもしれませんが、一度答えを聞いてしまえば、その答えは明らかになります。この比較（アナロジー）において、基本的な問題は、「なぞなぞは本当に私たちが思っているほど難しいものなのか、それとも私たちは何かを見落としているのか」ということです。

このようなP対NP問題は実用上非常に重要であるため、多くの数学者、科学者、コンピュータ・プログラマは、「すぐにチェックできる問題は、すぐにも解ける」という一般命題を証明したいと考えています。この問題は、クレイ数学研究所が、この問題を反証する証明や妥当な説明を成功させた人に100万ドルを与えるほど重要な問題です。

もう少し掘り下げると、P問題はすべてNP問題です。問題を解き、2つの解答を比較することで、解答が正しいことを簡単に確認することができます。しかし、人々はその反対のことを知りたがっています。P問題以外のNP問題はあるのか、それともNP問題はすべてP問題だけなのか。もし、NP問題が本当にP問題と同じではない（P≠NP）のであれば、そのNP問題を解く一般的で高速な方法は、いくら探しても存在し得ないことになります。しかし、もしNP問題がすべてP問題であるならば（P = NP）、新しい非常に高速な問題解決方法が存在することになります。私たちはまだそれを見つけていないだけなのです。

科学者や数学者の最善の努力によっても、NP問題を解くための一般的で簡単な方法はまだ見つかっていないので、多くの人は、P問題以外のNP問題が存在する（つまり、P≠NPが真である）と信じています。多くの数学者もこのことを信じていますが、現在のところ、厳密な数学的分析によってそれを証明した人はいません。もし、NPとPが同じであること（P＝NPが真であること）が証明されれば、日常生活の様々な面で大きな影響を与えることになります。そのため、P対NPの問題は重要なテーマであり、広く研究されています。

例

ある人が、質量の異なる石を積み上げて2つの塔を建てようとしたとします。このとき、それぞれの塔の質量がまったく同じになるようにしたいと思います。そのためには、石を同じ質量の2つの山に分けなければなりません。そのためには、同じ質量の石を2つに分けなければなりません。(答えを確認するには、石を2つの山に分けて、天秤を使って同じ質量になるかどうかを確認すればよい）。この問題はコンピュータ科学者の間では「Partition」と呼ばれていますが、チェックするのが簡単なので、後述するように、完全に解くよりも簡単なので、P問題ではありません。

どのくらい難しいのですか？100個の石を用意すると、2^{100-1}-1 = 633,825,300,114,700,748,351,602,687、つまり約6.3×10^{29}通りの石の分け方（組み合わせ）があることになります。もし、毎日1つの石の組み合わせを確認することができたら、1.3×10^{22}、つまり13億年の努力が必要になります。ちなみに、物理学者によれば、宇宙の年齢は約1.4×10^{10}年（450,000,000,000,000または約4.5×10^{17}秒、つまり私たちの石積み作業にかかる時間の約1兆分の1である。つまり、宇宙の始まりから経過した時間をすべて考慮すると、2兆（2,000,000,000,000）通り以上の石の分け方を1秒ごとにチェックしなければならないことになります。

強力なコンピュータをプログラムして、これらの岩石の分け方をすべてテストした場合、現在のシステムでは、1秒間に11,000000,000000個の組み合わせをチェックできるかもしれない。つまり、すべての岩石の分け方をテストするには、宇宙の起源から働いている、非常に強力なコンピュータ2が000まだ必要だということになる。

しかし、すべての組み合わせをチェックしなくても、石を2つの等しい山に分ける方法を見つけることができるかもしれません。PはNPに等しいか」という問いは、そのような方法が存在し得るかどうかを問う略語である。

なぜそれが重要なのか

NPの重要な問題の中には、可能性のあるすべての答えをテストするよりも速い方法で解決する方法を知らない人がたくさんいます。いくつか例を挙げてみましょう。

• 旅行中のセールスマンが、車で100都市を訪問したいと考えています。ガソリンには限りがあるので，合計10,000kmしか走れません．彼は，ガソリンを使い切ることなくすべての都市を訪れることができるかどうかを知りたい．
• ある学校では100種類のクラスがあり、教師は各クラスの期末試験に1時間を選ぶ必要があります。不正行為を防ぐために、ある授業を受けるすべての生徒は、その授業の試験を同時に受けなければなりません。もし生徒が複数のクラスを受講している場合、それらのクラスの試験はすべて異なる時間に行わなければなりません。先生は、すべての生徒がそれぞれのクラスの試験を受けられるように、すべての試験を同じ日にスケジュールできるかどうかを知りたいと考えています。
• ある農家の方が、質量の異なる100個のスイカを市場に持っていきたいと考えています。そのスイカを箱に詰めなければなりません。1つの箱には20キログラムしか入れられませんが、壊れません。100個のスイカを市場に持っていくのに、10個の箱で足りるかどうかを知りたいのです。(これは些細なことで、もし1個のスイカが2kg以上でなければ、10個のスイカをそれぞれの箱に入れることができ、もし10個のスイカが2kg以上でなければ、それぞれの箱に1個のスイカを入れることができるなど、迅速に解決することができます。）
• 大きな画廊にはたくさんの部屋があり、それぞれの壁には高価な絵画がたくさん飾られています。画廊のオーナーは、泥棒が絵画を盗もうとしたときのために、これらの絵画を監視するカメラを購入したいと考えています。彼は、それぞれの絵画を少なくとも1台のカメラで見ることができるようにするために、100台のカメラで十分であるかどうかを知りたいと考えています。
• 徒党問題：ある学校の校長は、どの生徒がお互いに友人であるかのリストを持っています。彼女は生徒の10%がお互いに友人であるグループを見つけたい。

指数時間

上の例では，100個100の石があるとき，石の集合を分割する方法は{{2100displaystyle 2^{100}}通りあることがわかる．n個の石があれば、n通りの2組み合わせがある。関数f ( n ) = n2 {\displaystyle f(n)=2^{n}}は，指数関数である．問題を解くのに必要な最悪の計算回数、つまり最悪の所要時間をモデル化しているので、NPにとって重要な関数である。

これまでのところ、難しい問題では、n2個の計算が必要であった。どのような問題であっても、人々は必要な計算数を減らす方法を見つけてきた。最悪の場合の計算数の1％だけで済む方法を考え出し、計算量を大幅に減らすことができるかもしれないが、それでも計算量は×0.01（n2）｛0.01times（2^{n}）｝になる。そして、岩が1つ増えるごとに、問題を解くために必要な計算回数は2倍になります。さらに少ない計算量でモデルのバリエーションを作る方法を生み出す洞察力がある。例えば、n 2/ n {displaystyle 2^{n}/n^{33}} ..しかし、nが大きくなっても指数関数が支配的である。

上述した試験のスケジューリングの問題を考えてみましょう。しかし、次に、15000人の学生がいるとします。15000人の学生全員のスケジュールを取得するコンピュータプログラムがあります。このプログラムは1時間で実行され、すべての学生が1週間で試験を受けられるような試験スケジュールを出力します。このプログラムは、試験週間のストレスを軽減するための多くのルール（連続した試験を行わない、28時間以内に2つ以上の試験を行わない、...）を満たしています。このプログラムは中間休みに1時間だけ実行され、全員が自分の試験スケジュールを知り、余裕を持って準備することができます。

しかし、次の年には生徒が10人増えている。同じコンピュータで同じプログラムを走らせると、1時間が2時間210になってしまう。つまり6、6週間である。もし、生徒が20人増えたとしたら

220  2^{20}}時間＝{{10485761048576}時間～{{4369143691}日～{113113}年

したがって、15000人15000の生徒には1時間。15020人15020の学生には、113年かかる。

ご覧のとおり、指数関数は非常に速く成長します。ほとんどの数学者は、NP問題の中で最も難しい問題は、指数関数的な時間を必要とすると考えています。

NP完全問題

数学者は、NP問題の中にもNP-Completeなものがあることを示すことができます。NP-Complete問題は、少なくとも他のNP問題と同じくらい解くのが難しい問題です。これは、もし誰かがNP-Complete問題を素早く解く方法を見つけたら、その同じ方法を使ってすべてのNP問題を素早く解けるということです。上に挙げた問題はすべてNP-Completeなので、もしセールスマンが旅行の計画を素早く立てる方法を見つけたら、それを先生に伝えれば、先生はその同じ方法を使って試験のスケジュールを立てることができます。農夫は同じ方法を使って必要な箱の数を決め、女性は同じ方法を使って塔を建てる方法を見つけることができるでしょう。

これらの問題の1つを素早く解決する方法は、すべての問題を解決することができるため、その方法を見つけたいと思っている人がたくさんいます。しかし、NP完全問題には非常に多くの種類があり、そのうちの一つでも素早く解く方法を見つけた人は今のところいないため、ほとんどの専門家はNP完全問題を素早く解くことは不可能だと考えています。

基本特性

計算複雑さの理論において、複雑さのクラスであるNP-complete（NP-CまたはNPCと略す）は、2つの性質を持つ問題のクラスである。

• NP(non-deterministic polynomial time)問題のセットに含まれる。与えられた問題の解答はどれも素早く（多項式時間で）検証できる。
• また、NP困難問題のセットにも入っています。NPの中で最も難しい問題と少なくとも同じくらい難しい問題。NP困難問題は、必ずしもNPの要素である必要はなく、実際、解読可能でない場合もあります。

形式的な概要

NP完全とは、多項式時間で解が検証できるすべての決定問題の集合であるNPの部分集合である。NPは、機械上で多項式時間で解かれる決定問題の集合と等価に定義することができる。NPに含まれる問題pは、NPに含まれる他のすべての問題が多項式時間でpに変換される場合に限り、NPCにも含まれる。NP-completeは形容詞として使われるようになり、NP-completeクラスの問題はNP+complete問題として扱われるようになった。

NP完全問題が研究されているのは、ある問題（NP）の解を素早く検証する能力が、ある問題（P）を素早く解く能力と相関があると考えられているからです。P = NP:問題セットと呼ばれるように、NPのすべての問題が素早く解けることがわかっています。NP完全問題の定義では，NPのすべての問題は，NP完全問題のすべての問題にすぐに還元できる（多項式時間で還元される）必要があるとされているため，NP完全問題の1つの問題は，NPのすべての問題がすぐに解けるよりも早く解かれる．[1]

例

論理的充足性問題はNP完全であることが知られている。1972年、リチャード・カープは、NP完全であることが知られている21の問題を定式化しました。これらは「カープの21のNP完全問題」と呼ばれている。整数に線形計画法を適用した整数計画問題、ナップザック問題、頂点被覆問題などがある。