形式陈述

语言 $L$ 属于 $\mathbf{NP}$，当且仅当存在多项式 $p$ 和多项式时间验证器 $V$，使

$$x\in L⟺\mathrm{\exists }c,|c|\le p(|x|)\wedge V(x,c)=1.$$

等价地，$L$ 可由非确定性图灵机在多项式时间内判定。

直觉

NP 描述“给出候选证据后可以快速检查”的问题，而不是“不是多项式时间”的缩写。

例子与边界

SAT 的满足赋值、哈密顿回路的顶点序列都可快速验证。$\mathbf{P}\subseteq \mathbf{NP}$；是否严格包含仍未知。

推论与应用

NP 完全性把大量搜索与优化问题的困难性联系在一起，是复杂度理论最核心的比较框架。

参考资料

• Sanjeev Arora and Boaz Barak, Computational Complexity: A Modern Approach, §2.1–2.2.
• Michael Sipser, Introduction to the Theory of Computation, 3rd ed., §7.3.