NP非确定性多项式时间¶

即非确定性多项式时间 (Non-deterministic Polynomial time)，是指可以用非确定性图灵机在多项式时间内计算出的问题。等价的另一种定义是其解的正确性能够在多项式时间内被检查的问题。
所谓非确定性，就是指可以同时做出多种选择并进行相应的计算，而只要在一种选择中计算结果是真，那么最终的计算结果就为真。一个便于理解的诠释是，NP 问题是一类可在多项式时间内验证你给出的答案是否正确的问题。
NP 相关的问题中一个重要概念是 NP-complete 问题: 如果对于某一个 NP 问题 L, NP 中所有的问题 A 都可以在多项式时间内``多一规约 (many-one reduction)`` 到 L，那么 L 就是一个 NP-complete 问题
从定义来说，如果 L 可以被高效地（即在多项式时间内）解决，那么所有 NP 中的问题都可以被高效地解决，也就是说 L 比 NP 中的所有问题都要 “难”。
这类问题本身就可以作为所有 NP 问题的代表，或者说它们是所有 NP 问题中最难的一部分。所以在研究 NP 与 P 间关系的时候，常见的一个着手点就是``对 NP-complete 问题进行分析``。

扩展¶