P与NP问题 是计算机科学和数学中最重要的未解难题之一。它探讨的是：所有能在多项式时间内验证解的问题，是否也能在多项式时间内求解？
核心概念
P类问题
- 能在确定性图灵机上以多项式时间（(O(n^k))，(k)为常数）解决的问题。
- 例子：
- 排序（(O(n \log n))）。
- 最短路径问题（Dijkstra算法，(O((V+E) \log V))）。
NP类问题
- 能在多项式时间内验证解，但未必能快速求解的问题。
- 例子：
- 布尔可满足性问题（SAT）——判断逻辑公式是否存在满足赋值。
- 旅行商问题（判定版）——判断是否存在成本≤(k)的路线。
- P ⊆ NP（能快速求解的问题必然能快速验证）。
NP完全问题
- NP中最难的问题，如果任何一个NP完全问题属于P，则P = NP。
- 例子：SAT、3-SAT、背包问题、哈密顿路径问题。
NP难问题
- 至少与NP完全问题难度相当，但未必属于NP。
- 例子：停机问题、旅行商问题的优化版本。
P vs NP的核心问题
- P是否等于NP？
- 若P = NP，则密码学、蛋白质折叠、定理证明等可验证问题均可高效求解。
- 若P ≠ NP，则某些问题的求解难度本质高于验证。
研究现状
- 多数科学家认为P ≠ NP，但尚未证明。
- 无论结果如何，其影响深远：
- 密码学：现行加密体系基于P ≠ NP的假设。
- 优化：若NP难问题可高效解决，将重塑物流、人工智能等领域。
- 数学：揭示计算能力的根本极限。
千禧年大奖难题
- 克雷数学研究所为此悬赏100万美元。