P≠NP予想とは？わかりやすく｜100万ドルの懸賞・NP完全・数独と巡回セールスマン

P≠NP予想とは？（ひとことで）

P≠NP予想（P対NP問題）とは、「答えを確かめるのが速い問題は、答えを見つけるのも速いのか」という、コンピューターの世界の最大の難問です。1971年にスティーヴン・クックが現在の形で提出し、2000年に米国のクレイ数学研究所が100万ドルの懸賞金をつけた7つの「ミレニアム懸賞問題」の1つに選ばれました。

ほとんどの専門家は「見つけるほうが本当にむずかしい（P≠NP）」と予想していますが、証明はまだありません。もし反対に「P＝NP」と分かれば、暗号はこわれ、数学の証明も機械が見つけられるようになるかもしれず、世の中が一変すると考えられています。

数独やパズルを解く、旅行の最短ルートを考える、といった身近な問題が、この予想の題材です。数独を解くのは大変でも、完成した盤面が正しいかを確かめるのは簡単です。この「差」が本当にあるのかを問うのが、P≠NP予想です。

うかるくん

「確かめるのは速い」のに「見つけるのは遅い」って、本当にそんな問題があるんですか？

合格先生

あるとみんな信じているんだ。たとえば数独。完成した盤面なら、各行・各列・各ブロックに1〜9が1つずつあるかを調べるだけで、1分もかからない。でも空白の多い盤面を一から解くのは、ずっと時間がかかる。ただ、「本当にどんなやり方でも速くならない」ことは、まだ誰も証明できていないんだよ。

P≠NP予想の意味をやさしく解説

「見つける」と「確かめる」

次の問題を考えてみましょう。「3, 34, 4, 12, 5, 2 の中から、いくつか選んで合計が9になる組はあるか」。

答えをもらえば、足し算1回で確かめられます。でも自分で探すとなると、数字が6個なら 2⁶＝64 通りの選び方があります。数字が50個なら、2⁵⁰＝約1.1×10¹⁵通りです。

P とは？NP とは？

• P：コンピューターが速く（多項式時間で）解ける問題の集まり。問題の大きさ n に対して、n²、n³ のような速さで増える手間で解けるもの。例：数をならべかえる、2つの数のかけ算、最大公約数（ユークリッドの互除法）。
• NP：答えがあれば速く確かめられる問題の集まり。例：数独、合計がちょうど9になる組、巡回セールスマン問題。

解けるなら確かめるのも速いので、P は NP の一部分です。問題は「NP の中に、P に入らない問題はあるか」、つまり P と NP が本当にちがうのかどうかです。

なぜ「速い」の基準が多項式なのか

手間の増え方には、大きな差があります。問題の大きさ n が大きくなったとき、n²（多項式）の手間は穏やかに増えますが、2ⁿ（指数）の手間は爆発的に増えます。

指数の計算には、指数法則と対数の公式が役立ちます。2ⁿ は n が10増えるごとに約1000倍（2¹⁰＝1024）になります。「どんなに速いコンピューターを作っても追いつけない」増え方だということです。

巡回セールスマン問題

「いくつかの都市を、すべて1回ずつまわって出発点にもどる最短ルートは？」という問題を、巡回セールスマン問題といいます。5都市なら、ルートは全部で 12 通りです。

都市が n 個のとき、ルートの数は (n−1)!÷2 通りです。順列・組合せの公式の考え方で数えられます。10都市で約18万通り、20都市なら 6.1×10¹⁶ 通りです。1秒に10億通り調べられるコンピューターでも、20都市で約1.9年かかります。しかも、「もっと短いルートがない」ことを確かめるのも難しいのです。これでも、「このルートの長さは何以下か」は足し算ですぐ確かめられます。ここが NP の性質です。

NP完全問題：1つ解ければ全部解ける

NPの中には、NP完全問題とよばれる「いちばん手ごわい」グループがあります。1つのNP完全問題を速く解く方法が見つかると、NPのすべての問題が速く解けて、P＝NP が証明されるという性質があります。

1971年にクックが、論理式が真になるように変数の値を決められるかを問うSAT（充足可能性問題）が NP完全であることを示しました（クック・レビンの定理）。翌1972年にリチャード・カープが、ナップサック問題、ハミルトン閉路（巡回セールスマン問題の仲間）、グラフの色ぬり分けなど、21の問題がNP完全だと示しました。四色問題で見た「地図が3色でぬれるか」を判定する問題も、NP完全問題の1つです。

NP完全問題は今では数千種類が知られており、数独（一般の大きさ n²×n²）、パズルの「スライディングパズル」、荷物のつめこみ（ナップサック問題）、時間割づくりなど、現実の問題がふくまれます。

数独で考えるNPの感覚

普通の 9×9 の数独は、盤面の大きさが決まっているので、理屈の上では有限の手間で必ず解けます。ところが、盤面を 16×16、25×25、…と大きくしていくと、必要な手間がどのくらい増えるのかが問題になります。一般の大きさの数独は、NP完全という仲間に入ることが知られています。つまり、盤面が大きくなると「だれでも使える速い解き方」はまだ見つかっていない、ということです。ただし、これはあくまでこれまでに見つかっていないという意味で、存在しないと証明されたわけではありません。この区別が、P≠NP予想の核心です。

身近な例は、ほかにもあります。クラスの席替えで、仲の悪い人どうしを隣にしない席の組み方を探す問題、遠足のバスにグループを割り振る問題なども、人数が増えると急に難しくなります。条件がやさしければ手で解けても、条件が増えるとコンピューターでも手に負えなくなる。これがNP完全問題の姿です。

P≠NP予想の歴史と年表

1955〜56年：手紙の中の予感

この問題の“原点”は、手紙の中にあります。1955年にナッシュの業績と生涯がアメリカ政府の機関に宛てた手紙の中で、暗号の鍵が長くなると、解読の手間は指数関数的に増えるはずだと書いていたことが、のちに知られました。1956年には、ゲーデルの業績と生涯が、フォン・ノイマンへの手紙で、「数学の定理の証明を、機械で速く見つけられるか」という問いをかいています。これは、P対NP問題の先ぶれだと考えられています。

1971年：クックの論文

1971年に、アメリカ生まれで、トロント大学（カナダ）で研究したスティーヴン・クックが論文「定理証明手続きの複雑さ」を発表し、SAT がNPの中で最も難しい問題であること（NP完全）を示しました。クックはこの業績などで、後に、コンピューター科学の最高の賞であるチューリング賞を受けています。ほぼ同じころ、ソビエト連邦のレオニード・レビンが、独立に同じ結果に到達しました（1973年の論文）。

1972年：カープの21問題

アメリカのリチャード・カープは、クックの結果を使って、組合せ最適化の21の有名な問題がNP完全であることを示しました。これで、この理論は一気に実用的な広がりをもちました。

1975年以降：解けない“壁”の発見

P≠NP を示すために、数学者たちは多くの方法をためしましたが、1975年に、ベイカー、ギル、ソロベイが「ある方法（相対化）では、P＝NPとP≠NPのどちらも示せてしまう」ことを示し、この方法の限界を明らかにしました。1993年には、ラズボロフとルディッチが「自然な証明」という大きな方法も、暗号が安全であるという仮定のもとでは、使えないことを示しました。さらに2008年には、アーロンソンとウィグダーソンが、「代数化」という方法にも限界があることを示しました。どんな方法でも証明できない“壁”が、いくつも見つかっていることが、この問題のむずかしさを物語っています。

2000年：100万ドルの懸賞問題

2000年5月24日、アメリカのクレイ数学研究所は、パリのコレージュ・ド・フランスで、7つのミレニアム懸賞問題を発表しました。各問題に100万ドルの懸賞金がつきます。P対NP問題はその1つで、問題の正式な説明はクックが書いています。ほかの6問のうち、ポアンカレ予想だけが解決され、リーマン予想やBSD予想などは未解決のままです。

P≠NP予想は今どこまで分かっている？（2026年10月時点）

P≠NP予想は未解決です。クレイ数学研究所の公式のページでも、2026年に確認できた範囲では「未解決」とされています。私たちは「いつ解けるか」を予想しません。ここでは、これまでに分かっていることと、分かっていないことを整理します。

みんなの予想：P≠NP

アメリカの計算機科学者ガサーチが専門家に行ったアンケートでは、「P≠NPだと思う」人の割合は、2002年の発表で61％、2012年の発表で83％、2019年の発表で88％と増えています。2019年の調査では、専門家の回答者のほぼ全員が「P≠NP」と答えたと報告されています。ただし、これは「みんなの予想」であって、証明ではありません。

分かっている結果

• NP完全問題がたくさんある：SATなど、数千種類の問題がNP完全だと分かっています。どれか1つが速く解ければ、P＝NPです。逆に、どれか1つでも速く解けないと証明できれば、P≠NPです。
• ラドナーの定理（1975年）：もしP≠NPなら、PでもNP完全でもない“中間”の問題が存在します。素因数分解（素因数分解）は、その候補と考えられていますが、確かではありません。
• 証明の方法の限界：相対化・自然な証明・代数化という3つの強力な方法では、この問題は解けないことが分かっています（上の年表のとおり）。

暗号と素因数分解

インターネットの暗号の多くは、大きな整数の素因数分解は難しいという予想にもとづきます。たとえば、RSA暗号（1977年に提案）は、2つの大きな素数のかけ算は簡単でも、かけた結果を素因数に分けるのは難しい、という性質を使います。素因数分解は「確かめるのは簡単（かけ算するだけ）」ですから NP に入りますが、NP完全かどうかは分かっていません。1994年にピーター・ショアが、量子コンピューターを使うと素因数分解が速く解けるという方法を発表しましたが、これが通常のコンピューターでのP対NPの答えを与えるわけではありません。

P＝NP を主張する論文について

インターネットには、P＝NP や P≠NP を証明したと主張する論文が数多く出ています。しかし、専門家に認められたものは、2026年10月時点で確かめられていません。査読をへていない主張は、そのまま信じないことが大切です。

合格先生

P≠NP の証明がなくても、「速く解けない」ことを前提に使われている技術はたくさんあるんだ。暗号が安全に使えるのも、その信頼のおかげ。入試でも、証明されていない前提を使ってはいけないよ。

P≠NP予想はなぜ難しいのか

1. 「どんなやり方でも」を相手にする

P≠NP を示すには、「世の中のあらゆるアルゴリズム（解き方）を使っても、NP完全問題は速く解けない」ことを示す必要があります。いま知られている解き方がうまくいかないと確かめるのではなく、まだ誰も思いついていない解き方も含めて、全部ダメだと言うのです。背理法の使い方で「速く解けたら矛盾する」と示したくても、矛盾をどうやって作るかが分かりません。

2. 壁が複数ある

先ほど書いたとおり、相対化・自然な証明・代数化という強力な方法がそれぞれ使えないことが証明されています。解けそうな方法のほとんどに、“壁”が見つかっているということです。

3. P＝NP の可能性も消えない

「P≠NP のはずだ」と専門家の多くが信じていても、これは信念です。逆に、これまで誰も思いつかなかった画期的な解き方が、いつか見つかる可能性を、数学として排除したわけではありません。ゴールドバッハ予想のように、「コンピューターで調べると正しそう」と「証明」はまったくちがう、という点は同じです。

4. 証明のむずかしさそのものの問題

この問題には、「証明を見つけること」自体が、P対NP問題の対象になるという、ふしぎな入れ子構造があります。「数学の証明を見つける問題」は、短い証明があるかどうかを問う、NPの問題だからです。P＝NPなら、数学者の仕事も機械に任せられるかもしれません。

サクラちゃん

結局、P≠NPって、予想なのにどうしてみんな信じているんですか？

合格先生

何十年もの間、世界中の優秀な人が数千種類のNP完全問題に挑んできて、誰も速い解き方を見つけられなかったんだ。1つでも速く解ければ全部解けるのに、それが起きない。だから「たぶん無理だ」と信じられている。でも信じることと証明することはちがう。だから100万ドルの賞金がかかっているんだよ。

受験・勉強とP≠NP予想のつながり

中学受験：場合の数と手間の増え方

中学受験の「場合の数」で、並べ方や選び方が何通りあるかを数える練習は、P≠NP予想の入り口です。2つの選択を n 回くり返すと 2ⁿ 通り、n 人を1列に並べると n! 通りです。この増え方が、手間の指数的な増加を生みます。順列・組合せの公式（nPr・nCr）をしっかり身につけましょう。

高校受験・大学受験：数列と指数・対数

2ⁿ の増え方は、数列（等比数列）の問題とつながります。たとえば「2ⁿ が10¹²を超える最小の n は何か」という問題は、常用対数とけた数で解けます（2⁴⁰＝約1.1×10¹²、答えは n＝40）。常用対数とけた数の問題の解き方も参考にしてください。

大学入試・情報：アルゴリズム

プログラミングの授業では「計算量」を学びます。n 個のデータを並べかえるには n×log n 回程度の手間ですむ（P）のに、すべての組み合わせをためすと 2ⁿ 回の手間がかかる、というちがいが重要です。2025年1月からの大学入学共通テストでは「情報」も教科に加わりました。

勉強法として

P≠NP予想の教えは、「確かめる」と「見つける」は別の力だということです。入試の数学でも、答えが出たあとで検算（確かめる）ことは速くできます。検算の習慣は、見つける力と同じくらい大切です。数学の勉強法（解法の暗記→演習→過去問）で、答えを確かめる習慣のつけ方も紹介しています。

P≠NP予想が数学・社会にあたえる影響

• 暗号の安全性：インターネットの買い物や銀行の通信を守る暗号は、「ある種の問題は速く解けない」という信頼の上に成り立っています。もしP＝NP が示され、速い解き方まで見つかれば、多くの暗号が破られる可能性があります。
• 最適化の革命：もしP＝NPなら、配送ルート、工場の生産計画、時間割、タンパク質の形の予測など、多くの最適化問題が、一気に速く解けるようになります。
• 数学の自動化：数学の証明を見つける問題がNPに入るため、P＝NPなら、短い証明がある定理は機械が見つけられることになります。
• 計算量理論の発展：この問題を研究する中で、NP完全性、近似アルゴリズム、乱択アルゴリズム、量子計算の理論が育ちました。

リーマン予想やコラッツ予想と並び、P≠NP予想は「簡単に述べられるのに、解けない」問題の代表です。チューリングの業績と生涯が築いた計算の理論は、いまも新しい問いを生み続けています。

P≠NP予想に挑戦！練習問題

P≠NP予想と関係する数学者・難問

• チューリングの業績と生涯：「計算とは何か」を数学で定めた先駆者です。
• ゲーデルの業績と生涯：1956年の手紙で、P対NP問題の先ぶれとなる問いを書きました。
• フォン・ノイマンの業績と生涯：ゲーデルの手紙の宛先で、コンピューターの基礎を築きました。
• ナッシュの業績と生涯：1955年の手紙で、暗号の難しさについて予感を書いていました。
• リーマン予想・四色問題・ABC予想：ミレニアム懸賞問題やコンピューターの証明でつながる難問です。

ほかの未解決の難問

• 奇数の完全数はあるかとは（未解決）
  6・28のように約数の和が自分の2倍になる完全数。偶数のものは52個見つかっているが、奇数の完全数は1つも見つかっていない
• ゴールドバッハ予想とは（未解決）
  4以上の偶数は2つの素数の和で表せるか。とても大きな数まで確かめられているが証明はない（奇数版の「弱い予想」は2013年に証明が発表された）
• 双子素数予想とは（未解決）
  3と5、11と13のように差が2の素数の組は無限にあるか。2013年に「差が7000万以下の組は無限」と分かり、その後246まで縮まった
• リーマン予想とは（未解決）
  ゼータ関数の「自明でない零点」は、すべて実部が1/2の直線上にあるか。素数の分布のかぎ。ミレニアム懸賞問題
• コラッツ予想とは（未解決）
  偶数なら2でわり、奇数なら3倍して1を足す。どんな数から始めても1にたどり着くか

← 前の時代：コラッツ予想とは（未解決）　｜　次の時代：ABC予想とは（解決と発表・評価が分かれる） →

数学の難問・未解決問題の一覧（いつ・だれが解いたか）　｜　有名な数学者一覧

読みもの（合格大作戦の数学の記事）

• 算数・数学の公式一覧（公式辞典）
  公式・証明・例題を1つずつ
• 数学用語辞典（用語の意味を1語1ページ）
  素数・漸近線など200語
• 常用対数とけた数の問題の解き方
  国公立大学2次の頻出問題
• 数学の勉強法（解法の暗記→演習→過去問）
  青・黄・赤チャートの使い分け
• 京大理系数学の出題分析（1999〜2026年度）
  大問別一覧と頻出分野ランキング
• フェルマーの最終定理とは？わかりやすく解説
  n＝2と3以上の違い、ワイルズの証明

よくある質問

あわせて読みたい

• 数学の難問・未解決問題の一覧
• 有名な数学者一覧
• 算数・数学の公式一覧（公式辞典）