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

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

よくある質問
- 解かれた?
- いいえ。未解決です。
ジグソーパズルを完成させるのは何時間もかかるのに、確かめるのは数秒。この差は本物?

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

この理論だけを扱った資料はまだありませんが、CampusDown 資料室(韓国語)で関連レポートを検索できます。
レポートをもっと探す・「P 대 NP 문제」の検索結果 →この記事は2026年11月20日に最終更新されました。内容は広く知られた原典と教科書に基づいて整理していますが、レポートで引用する際は参考文献の原典を必ず確認してください。