# P vs NP 问题

> 千禧年七大数学难题之首

- ID: m02940
- 分类: technical
- 领域: 物理学

## 定义

千禧年七大数学难题之首。- P问题：计算机可以在多项式时间（合理时间）内解决的问题（如乘法、排序）。- NP问题：计算机可以在多项式时间内验证答案的问题（如数独、拼图、密码破解）。- 核心困境：P是否等于NP？即"如果一个问题的答案很容易验证，那么找到这个答案是否也很容易？"目前普遍认为P≠NP。- 脚手架作用：效率的物理极限。它告诉我们

## 机制

P 类问题可被多项式时间"求解"，NP 类问题可被多项式时间"验证"答案。核心问题是 P=NP 是否成立：若成立，则所有易验证的问题都易求解（密码学崩溃、优化普解）；若不成立（主流信念），则存在"验证易、求解难"的本质鸿沟。它是计算复杂度的根本分界。

## 练习

1. 面对问题，判断它属 P（有高效算法）还是 NP（只有高效验证）。 2. 若疑似 NP-hard，放弃求最优，改用近似 / 启发式。 3. 在安全设计中利用 P≠NP 假设（如密码哈希）。 4. 把"指数级爆炸"作为不可解的信号。

## 脚手架用法

效率的物理极限。它告诉我们

[阅读网页](https://thinkingmodels.site/entries/detail/m02940)