【数学基础】P问题-NP问题-NP-c问题-NP-hard问题常见辨析

P问题、NP问题、NP-complete问题和NP-hard问题是计算机科学中关于计算复杂性的重要概念。在日常学习和工作中经常用到，常常感到迷糊，近日乘着辨析整理了下。下面是它们的基本概念、相互关系，以及典型示例：

P问题（Polynomial Time）：

如果一个问题可以在多项式时间内解决，即问题的输入规模n的某个固定次方的时间内解决，那么这个问题就被称为P问题。例如，排序问题和查找问题都是P问题。

NP问题（Non-deterministic Polynomial Time）：

如果一个问题可以在多项式时间内验证其解的正确性，那么这个问题就被称为NP问题。这里的“非确定性”指的是在验证解的正确性时，可以使用一些猜测或者非确定性的方法。例如，旅行商问题和图的着色问题都是NP问题。

NP-complete问题：

NP-complete问题是NP问题的一个子集，它具有以下两个性质：
a) 它是一个NP问题。
b) 如果任何一个NP问题可以在多项式时间内转化为它，那么它就是一个NP-complete问题。
换句话说，如果一个NP问题解决了，那么所有的NP问题都可以在多项式时间内解决。因此，NP-complete问题是NP问题中最难的问题。例如，图的着色问题和哈密尔顿回路问题都是NP-complete问题。

NP-hard问题：

如果一个问题至少和任何一个NP问题一样难，那么这个问题就被称为NP-hard问题。换句话说，如果一个NP-hard问题解决了，那么所有的NP问题都可以在多项式时间内解决。但是，NP-hard问题本身不一定是一个NP问题。例如，图的同构问题和子集和问题都是NP-hard问题。

相互关系：

P问题是NP问题的一个子集，因为所有可以在多项式时间内解决的问题都可以在多项式时间内验证其解的正确性。NP-complete问题是NP问题的一个子集，因为它满足NP问题的定义，并且具有特殊的性质。所有的NP-complete问题都是NP-hard问题，但并非所有的NP-hard问题都是NP-complete问题。

典型示例：

P问题：排序问题、查找问题。
NP问题：旅行商问题、图的着色问题、背包问题。
NP-complete问题：图的着色问题、哈密尔顿回路问题、3-SAT问题。
NP-hard问题：图的同构问题、子集和问题、0-1背包问题。