CampusDownWiki
累計引用 126,015한국어KO 12,862EnglishEN 77,490日本語JA 9,775中文ZH 25,888
CampusDown(韓国語)↗
日本語

P対NP問題

➗ 数学・統計 執筆 CampusDown ウィキ編集部 最終更新 閲覧 1
P対NP問題は、提示された答えをすばやく確認できる問題は、すばやく解くこともできるのかという問いです。クレイ数学研究所の7つのミレニアム懸賞問題の一つです。
目次
  1. 1. PとNP
  2. 2. よくある質問
  3. 3. 参考文献

ジグソーパズルを完成させるのは何時間もかかるのに、確かめるのは数秒。この差は本物?

一人の学生が散らばったジグソーパズルに顔をしかめ、もう一人が完成したパズルを虫眼鏡で落ち着いて確かめるイラスト
解くのは大変、確かめるのは一瞬。

PとNP

Pはすばやく解ける問題、NPは答えをすばやく確認できる問題です。1971年にクックとレビンがそれぞれ定式化し、2000年にクレイ数学研究所がミレニアム懸賞問題(各100万ドル)に選びました。

PとNPの比較:Pは並べ替えのようにすばやく解ける問題、NPは完成した数独のように答えをすばやく確認できる問題
速く解く vs 速く確かめる。

よくある質問

解かれた?
いいえ。未解決です。

参考文献

  1. Clay Mathematics Institute. P vs NP.
  2. Clay Mathematics Institute. The Millennium Prize Problems.

役に立ったらシェアしてください

必要な友だちに送ってみましょう。

X Facebook Threads

この理論を使ったレポート・資料(韓国語)

この理論だけを扱った資料はまだありませんが、CampusDown 資料室(韓国語)で関連レポートを検索できます。

レポートをもっと探す・「P 대 NP 문제」の検索結果 →

あわせて読みたい理論

この記事は2026年11月20日に最終更新されました。内容は広く知られた原典と教科書に基づいて整理していますが、レポートで引用する際は参考文献の原典を必ず確認してください。