P,NP,NP-complete和NP-hard问题

2017年07月14日

1. 问题描述

1.1 多项式时间复杂度

首先,要说到的是多项式时间复杂度,时间复杂度是指执行算法所需要的计算工作量,其并不是表示一个程序解决问题需要花多少时间,而是当问题规模扩大后,程序需要的时间长度增长得有多快。

因此,如果一个算法,它能在以输入规模为参变量的某个多项式时间内给出答案,则称它为多项式时间算法。其中,多项式的复杂度有 等,其规模n出现在底数的位置;非多项式级的复杂度有 等。
1.2 P类问题 & NP问题

P类问题指的是:如果一个问题可以找到一个能在多项式的时间里解决它的算法,那么该问题就属于P问题,其中P指的是Polynomial(多项式)。

NP问题是指Non-deterministic Polynomial的问题,多项式复杂程度的非确定性问题,即可以在多项式的时间里验证一个解的问题,或者定义为,可以在多项式的时间里猜出一个解的问题。

所有非确定多项式问题的集合用NP表示,显然,所有的P问题都是NP问题

1.3 NP-complete问题

NP-complete问题是指:如果任何一个NP问题都能通过一个多项式时间算法转换为某个NP问题,那么这个NP问题就称为NP完全问题。根据其定义,满足其两个条件的问题,就是NP-complete问题:第一,它是个NP问题;第二,所有的NP问题都可以约化到它,其中约化表示一个问题A可以约化为问题B的含义即是,可以用问题B的解法解决问题A,或者说,问题A可以“变成”问题B。

因此,证明一个问题是NPC问题的步骤,先证明其是一个NP问题,再证明其中一个已知的NPC问题能约到到它。

NPC问题可以描述为,对于判定问题A,若A∈NP且NP中的任何一个问题可在多项式时间内归约为A,则称A为NP完全问题(NP-Complete或NPC).可以表示为A ∈ NPC。

1.4 NP-hard问题

NP-hard问题,即NP-hard,non-deterministic polynomial-time hard,其定义为:某问题被称作NP困难,当且仅当存在一个NP完全问题可以在多项式时间规约到这个问题。

因为NP困难问题未必可以在多项式的时间内验证一个解的正确性(即不一定是NP问题),因此即使NP完全问题有多项式时间内的解,NP困难问题依然可能没有多项式时间内的解。因此NP困难问题“至少与NPC问题一样难”。

NPH问题可以描述为,对于判定问题A,若NP中的任何一个问题可在多项式时间归约为判定问题A,则称A为NP困难问题(NP-hard 或NPH) .可以表示为A ∈ NPH。

2. P,NP,NP-complete和NP-hard问题之间的关系

NPC和NP-hard两者的区别是:验证一个问题A是否为NP-hard无须判断A是否属于NP. 根据定义可知NPC ∈ NPH。

NP-hard不一定是NP,比NPC问题的范围广。

NPC是NP问题,是NP-hard问题。

因此,他们之间的关系如下:

NP 01

如考虑P=NP的情况,则它们的关系如下:

NP 02

其中,NP和NP-hard问题的交集是NP-complete,P问题也在NP里面。

3. 实例

P类问题:排序算法问题(sorting),可以求出算法的复杂度为多项式复杂度;

NP问题:假如一件问题要处理的时间非常大,不是多项式时间内可以完成的,但是他可以透过无限的计算器去算,最终计算时间复杂度只有 ,那么它就是NP(非确定性多项式时间)问题。还有一个例子,输出n个元素的全排列,也是一个NP问题。

NP-complete问题:寻找哈密顿图路径问题(Hamiltonian path,or Traceable path),其解释为:寻找哈密顿路的确定算法虽然很难有多项式时间的,但是这并不意味着只能进行时间复杂度为O(n!n)暴力搜索。利用状态压缩动态规划,可以将时间复杂度降低到O(2^nn^3),具体算法是建立方程f[i][S][j],表示经过了i个节点,节点都是集合S的,到达节点j时的最短路径。每次都按照点j所连的节点进行转移。另外,01背包问题,也是NP完全问题。

NP-hard问题:SAT(此处暂时存在疑问)

下次,再找机会,学习学习NP相关问题的证明方法和步骤。

参考文献:

【1】算法导论自学笔记(8),http://zhangxiaoyang.me/categories/intro-to-algorithms-tutorial/intro-to-algorithms-tutorial-8.html

【2】論P,NP,NP-hard,NP-complete問題,http://bluelove1968.pixnet.net/blog/post/222283186-%E8%AB%96p%2Cnp%2Cnp-hard%2Cnp-complete%E5%95%8F%E9%A1%8C

【3】怎么理解 P 问题和 NP 问题,https://www.zhihu.com/question/27039635

【4】P vs. NP:从一则数学家谋杀案说起,http://www.guokr.com/article/437662/

【5】P/NP/NPC/NP-hard,http://yang19890314.blog.51cto.com/1620466/1160588

【6】哈密顿图,https://zh.wikipedia.org/wiki/%E5%93%88%E5%AF%86%E9%A1%BF%E5%9B%BE

【7】P问题、NP问题、NPC问题的概念即实例证明,http://www.2cto.com/kf/201605/511207.html

【8】NP (复杂度),https://zh.wikipedia.org/wiki/NP_(%E8%A4%87%E9%9B%9C%E5%BA%A6)

【9】NP难问题求解综述,http://www.cnblogs.com/yymn/p/4853747.html


版权声明:本文为博主原创文章,转载请注明出处 本文总阅读量