CampusDownWiki
累计引用 126,015한국어KO 12,862EnglishEN 77,490日本語JA 9,775中文ZH 25,888
CampusDown(韩语)↗
简体中文

P与NP问题

➗ 数学与统计 作者 CampusDown 维基编辑部 最后更新 浏览 1
P与NP问题是计算机科学最大的未解问题之一:如果一个答案能被快速验证,这个问题能否也被快速求解?它是克雷数学研究所七个千禧年大奖难题之一。
目录
  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日。内容依据公认的原著和教科书整理;在报告中引用时,请务必核对下方参考文献中的原始出处。