P vs NP：算法世界里那道"世纪难题"
有些问题我们知道"验证答案很快"，却不知道"找出答案多快"。P 是否等于 NP，是千年算力分界，也是图灵奖级别的开放问题。
算法世界有一道至今无人能解的悬案：P = NP 吗？ 它不仅是理论问题，更关乎"哪些事原则上能高效算、哪些永远算不动"。这道难题被列为千禧年七大难题之一，悬赏百万美元。
先厘清概念。P 是"能在多项式时间内求解"的问题类（如排序、最短路径）；NP 是"给定答案，能在多项式时间内验证对错"的问题类（如数独、旅行商路径）。显然 P ⊆ NP——能快速解，自然能快速验。真正的问题是：反过来成不成立？如果 P=NP，意味着所有"易验证"的问题也都"易求解"，那密码学、优化、调度将被彻底改写。
更精彩的是 NP 完全（NPC） 的概念（缺口 I1）：存在一批"最坏中的最坏"问题，只要其中一个能被多项式求解，所有 NP 问题就都能。典型代表是 SAT（判断一组逻辑公式能否同时为真）。CLRS 第34章展示了如何把一个问题归约到另一个，从而证明"它至少和 NPC 一样难"。
绝大多数计算机科学家猜想 P≠NP——即存在"易验证但本质上难求解"的问题。这正是我们今天仍依赖加密（基于"质因数分解难"）、仍用近似/启发式去逼近 NP 难优化问题的根本原因。理解 P/NP，你就理解了算法能力的"天花板"在哪里。
P/NP 是必学必会算法轨道里尚未补齐的核心缺口（I1），也是整个复杂性理论的入口。它提醒我们：算法不只是"怎么算更快"，更是"什么能算、什么算不动"的边界探索。
关联推荐
- GPT-5.6 递归自我改进 — 计算能力的边界，是算法与 AI 共同的话题
- （本批「算法与问题求解入门」KU 发布后回填互链）
评论 (0)
正文划词可点「问萝卜特」——自动发评论并由 AI 回复
加载评论中…