前言

在讨论这一串问题之前，我们需要复习两个概念。

1.多项式和非多项式

多项式：

非多项式：或者

2.时间复杂度

在计算机算法求解问题当中，经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小。时间复杂度则表示这个算法运行得到想要的解所需的计算工作量。这里探讨的是当输入值(也就是问题数目N，或者是待求解的问题)接近无穷时，算法所需工作量的变化快慢程度。

举例：冒泡排序

在计算机当中，排序问题是最基础的，将输入按照大小或其他规则排好序，有利于后期运用数据进行其他运算。冒泡排序就是其中的一种排序算法。假设手上现在有n个无序的数(N个待排序的问题)，利用冒泡排序对其进行排序。
①首先比较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变
②)接着比较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变
③一直向下比较直到第n-1和第n个数比较完，第一轮结束。(这时候最大的数移动到了第n个数的位置)
④)重复前三步，但是只比较到第n-1个数(将第二大的数移动到第n-1个数位置)
⑤持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

举个实例：5,4,3.2,1，对其进行排序，先是比较5跟4变成4,5,3,2,1，第一轮结束后变成4,3,2,1,5，可以计算，当对其排序完正好要经过4+3+2+1=10次比较，当然这是最复杂的情况，即完全反序。可以知道对于n个数，至多要经过1+2+…+n-1即(n^2-n)/2次比较才能排好序。这个式子里n的最高次阶是2，可以知道当

^{n时，一次性对其比较次数影响很小，所以我们把这个算法的时间复杂度比作：取其最高次，可以看出，这是一个时间复杂度为多项式的表示方式。}

另外一些穷举类的算法，所需时间长度成几何阶数上涨，这就是的指数级复杂度，甚至的阶乘级复杂度。它是非多项式级的，其复杂度计算机往往不能承受。

当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

正文

1、P问题

P问题:能够在多项式时间内被解决的问题。
比如说，给10个、20个、30个.…元素(问题)排序，复杂度是

2、NP问题

NP问题:能够在多项式时间内使用非确定性算法(non-deterministic)被解决的问题。
NP问题也可以指在多项式的时间里验证一个解的问题。另一个定义是，可以在多项式的时间里猜出一个解的问题。
简单来说就是，必须以非常规方法才能在多项式时间内解决的问题，就叫做NP问题。

举个例子:

我人品很好，在程序中需要枚举时，我可以一猜一个准。

现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少?

我说，我人品很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。

于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。

验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我运气好，猜得准，我一定能在多项式的时间里解决这个问题。这就是NP问题。

 

3、NP-complete问题(即:NP完全问题)

NP-Complete 满足两个条件:
1.首先它是一个NP问题
2.所有的NP问题都可以约化(Reducible)到它，NPC问题目前没有多项式的有效算法，只能用指和数级甚至阶乘级复杂度的搜索

 

约化：例如，求解一个一元一次方程 AAA 和求解一个一元二次方程 BBB，你若会求解 BBB，你一定会求解 AAA。那么我们说，A可以约化为 B。B BB 的时间复杂度高于或者等于 AAA的时间复杂度。

 

NP问题中最困难的问题称之为NP完全问题(NP-complete)。根据库克定理，任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决。
一般来说，非常规方法既可以解决P问题，也可以解决NP问题，所以，只有用非常规方法才能解决的问题，才能叫做NP完全问题。

示例:旅行商问题。就是一个NP完全问题，因为其开销不能在多项式时间内解决，而是一个非多项式时间复杂度的问题。

4、NP-Hard问题（即：NP难问题）

NP-Hard问题：和NP问题一样困难，或者更加困难的问题。
NP hard 满足 NPC 的第二条件，但不一定是 NP 问题。

因为它不一定是NP问题。即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上，由于 NP-Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

 

以上四个问题他们之间的关系可以用下图来表示：

 

 

 

 

---

本文转自CSDN平台博主：真难学啊
版权声明:本文为博主原创文章，遵循CC4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接:https://blog.csdn.net/sky_ying/article/details/129207606

 

前言

在讨论这一串问题之前，我们需要复习两个概念。

1.多项式和非多项式

多项式：

非多项式：或者

2.时间复杂度

在计算机算法求解问题当中，经常用时间复杂度和空间复杂度来表示一个算法的运行效率。空间复杂度表示一个算法在计算过程当中要占用的内存空间大小。时间复杂度则表示这个算法运行得到想要的解所需的计算工作量。这里探讨的是当输入值(也就是问题数目N，或者是待求解的问题)接近无穷时，算法所需工作量的变化快慢程度。

举例：冒泡排序

在计算机当中，排序问题是最基础的，将输入按照大小或其他规则排好序，有利于后期运用数据进行其他运算。冒泡排序就是其中的一种排序算法。假设手上现在有n个无序的数(N个待排序的问题)，利用冒泡排序对其进行排序。
①首先比较第1个数和第2个数，如果后者>前者，就对调他们的位置，否则不变
②)接着比较第2个数和第3个数，如果后者>前者，就对调他们的位置，否则不变
③一直向下比较直到第n-1和第n个数比较完，第一轮结束。(这时候最大的数移动到了第n个数的位置)
④)重复前三步，但是只比较到第n-1个数(将第二大的数移动到第n-1个数位置)
⑤持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

举个实例：5,4,3.2,1，对其进行排序，先是比较5跟4变成4,5,3,2,1，第一轮结束后变成4,3,2,1,5，可以计算，当对其排序完正好要经过4+3+2+1=10次比较，当然这是最复杂的情况，即完全反序。可以知道对于n个数，至多要经过1+2+…+n-1即(n^2-n)/2次比较才能排好序。这个式子里n的最高次阶是2，可以知道当

^{n时，一次性对其比较次数影响很小，所以我们把这个算法的时间复杂度比作：取其最高次，可以看出，这是一个时间复杂度为多项式的表示方式。}

另外一些穷举类的算法，所需时间长度成几何阶数上涨，这就是的指数级复杂度，甚至的阶乘级复杂度。它是非多项式级的，其复杂度计算机往往不能承受。

当我们在解决一个问题时，我们选择的算法通常都需要是多项式级的复杂度，非多项式级的复杂度需要的时间太多，往往会超时，除非是数据规模非常小。

正文

1、P问题

P问题:能够在多项式时间内被解决的问题。
比如说，给10个、20个、30个.…元素(问题)排序，复杂度是

2、NP问题

NP问题:能够在多项式时间内使用非确定性算法(non-deterministic)被解决的问题。
NP问题也可以指在多项式的时间里验证一个解的问题。另一个定义是，可以在多项式的时间里猜出一个解的问题。
简单来说就是，必须以非常规方法才能在多项式时间内解决的问题，就叫做NP问题。

举个例子:

我人品很好，在程序中需要枚举时，我可以一猜一个准。

现在某人拿到了一个求最短路径的问题，问从起点到终点是否有一条小于100个单位长度的路线。它根据数据画好了图，但怎么也算不出来，于是来问我：你看怎么选条路走得最少?

我说，我人品很好，肯定能随便给你指条很短的路出来。然后我就胡乱画了几条线，说就这条吧。那人按我指的这条把权值加起来一看，嘿，神了，路径长度98，比100小。

于是答案出来了，存在比100小的路径。别人会问他这题怎么做出来的，他就可以说，因为我找到了一个比100 小的解。在这个题中，找一个解很困难，但验证一个解很容易。

验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。那么，只要我运气好，猜得准，我一定能在多项式的时间里解决这个问题。这就是NP问题。

 

3、NP-complete问题(即:NP完全问题)

NP-Complete 满足两个条件:
1.首先它是一个NP问题
2.所有的NP问题都可以约化(Reducible)到它，NPC问题目前没有多项式的有效算法，只能用指和数级甚至阶乘级复杂度的搜索

 

约化：例如，求解一个一元一次方程 AAA 和求解一个一元二次方程 BBB，你若会求解 BBB，你一定会求解 AAA。那么我们说，A可以约化为 B。B BB 的时间复杂度高于或者等于 AAA的时间复杂度。

 

NP问题中最困难的问题称之为NP完全问题(NP-complete)。根据库克定理，任意一个NP完全问题如果能够在多项式时间内解决，则所有的NP问题都能在多项式时间内解决。
一般来说，非常规方法既可以解决P问题，也可以解决NP问题，所以，只有用非常规方法才能解决的问题，才能叫做NP完全问题。

示例:旅行商问题。就是一个NP完全问题，因为其开销不能在多项式时间内解决，而是一个非多项式时间复杂度的问题。

4、NP-Hard问题（即：NP难问题）

NP-Hard问题：和NP问题一样困难，或者更加困难的问题。
NP hard 满足 NPC 的第二条件，但不一定是 NP 问题。

因为它不一定是NP问题。即使 NPC 问题发现了多项式级的算法，NP-Hard 问题有可能仍然无法得到多项式级的算法。事实上，由于 NP-Hard 放宽了限定条件，它将有可能比所有的 NPC 问题的时间复杂度更高从而更难以解决。

 

以上四个问题他们之间的关系可以用下图来表示：

 

 

 

 

---

本文转自CSDN平台博主：真难学啊
版权声明:本文为博主原创文章，遵循CC4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

原文链接:https://blog.csdn.net/sky_ying/article/details/129207606