P NP NPC NP-Hard co-NP 问题

  P 问题： P 问题就是指能在多项式时间求解出的问题。举个例子：排序问题，二分查找问题的时间复杂度分别是 O(nlogn)，O(logn)。

  说到时间复杂度，下面给出时间复杂度的解释：
  时间复杂度并不是表示一个程序解决问题需要花多少时间，而是当问题规模扩大后，程序需要的时间长度增长得有多快。也就是说，对于高速处理数据的计算机来说，处理某一个特定数据的效率不能衡量一个程序的好坏，而应该看当这个数据的规模变大到数百倍后，程序运行时间是否还是一样，或者也跟着慢了数百倍，或者变慢了数万倍。不管数据有多大，程序处理花的时间始终是那么多的，我们就说这个程序很好，具有 O(1) 的时间复杂度，也称常数级复杂度；数据规模变得有多大，花的时间也跟着变得有多长，这个程序的时间复杂度就是 O(n)，比如找 n 个数中的最大值；而像冒泡排序、插入排序等，数据扩大 2 倍，时间变慢 4 倍的，属于 O(n^2) 的复杂度。”

  NP 问题：就是不能确定是否能够在多项式时间内找到一个解。但若给出一个解，能在多项式时间内证明这个解是否正确（学名叫判定性问题）。定义的前半句有两层含义：可能找得到解，也可能找不到解。找得到解问题就变成了 P 问题。所以 P 问题属于 NP 问题（P 问题是 NP 问题的真子集）。

  NPC 问题：说到 NPC 问题，就要提到一个操作叫 “规约”。这里有一个易受误导的地方，规约不是越化越简单，反而是越化越难。举个例子：A 是求解一元一次函数，B 是求解一元二次函数。可以说 A 可规约至 B，因为会解 B，一定会解 A。可把 A 看作是二次项系数为 0 的 B。所以，每规约一步，问题就变得越复杂。规约具有传递性：A 规约至 B，B 规约至 C，那么 A 规约至 C。问题来了，那么一直规约下去会得到什么呢？这就是 NPC 问题。

  NPC 问题上文有所介绍，它是由 NP 问题不断规约得来。首先 NPC 本身是一个 NP 问题，这是证明一个问题是 NPC 问题的首要条件。有 NPC 和 NP 问题之间的关系，可以看出：如果一个 NPC 问题得到了证明，那么所有可以规约至该 NPC 的 NP 问题都得到了证明。到目前为止，部分 NPC 问题得到了证明，但还有很多未证明。也有人把这些问题称之为信息学的 “巅峰”。下面介绍一下证明一个问题是 NPC 问题的方法：
  第一步：证明这个问题是一个 NP 问题；
  第二步：证明一个已知的 NP 问题能够规约到该问题。

  NP-Hard 问题：就是满足 NPC 问题的第二个条件，但是却不一定满足第一个条件的问题。任意 NP 问题都可以在多项式的时间内规约至 NP-Hard 问题。但像上文说的，NP-Hard 问题不一定是 NP 问题。通俗点说，NP-Hard 问题就是至少和 NPC 问题一样难。可能是 NPC 也可能不是 NPC（这取决于 NP-Hard 问题是否为 NP 问题）。

  co-NP 问题：是由补问题属于 NP 问题的问题组成。

  NPI 问题：是 NP 问题中不包含于 P 问题和 NPC 问题的问题（P 属于 NPI）。