P、NP、NP完全问题

如果一个算法的最差时间效率属于O(p(n)),则该算法可以在多项式的时间内对问题进行求解,其中p(n)是输入规模n的一个多项式函数。

可以在多项式时间内求解的问题是易解的。不能在多项式时间内求解的问题是难解的

判定问题是能够回答是或否的问题,通常第一,只有判定问题才属于P。

P类问题是一类能够用确定性的算法,在多项式的时间内求解的判定问题,这种问题类型也称为多项式类型。

为什么要将P约束为判定问题?

1、不能在多项式时间内求解的问题会产生指数级的巨大输出。

2、许多重要问题可以化简为一系列更容易研究的判定问题。

并不是每一个判定问题都能够在多项式的时间内求解,某些判定问题是不能用任何算法求解的,这种问题成为不可判定的问题。这是相对于用算法求解的可判定问题来说的。不可判定问题,我们称它为停机问题:给定一段计算机程序和它的一个输入,判断对于该输入是会终止,还是会无限的运行下去。

存在可以判定,但又难解的问题。也有许许多多的重要问题,我们竟没有找到它的多项式类型算法,也无法证明这样的算法不存在。比如哈密顿回路问题,旅行商问题,背包问题,划分问题,装箱问题,图的着色问题,整数线性规划问题。这些问题中有一些是判定问题,另一些不是判定问题,都可以转化为等价的判定问题,这些问题的共同点是,他们都有着按这指数增长的候选项,其规模是输入规模的函数,我们需要在这些候选项中寻找问题的最终结。其次,虽然在计算机上对问题的求解可能是困难的,但是在计算上判定一个待定解是否解决了该问题,就是简单的,这种判定可以在多项式时间内完成。

一个不确定算法是一个两阶段过程,他把一个判定问题的实例l作为它的一个输入,并进行下面的操作:

  非确定阶段,生成一个任意串s,,把它当作给定实例的一个候选解。

  确定阶段,确定算法把l和s都作为它的输入,如果s的确是l的一个解,就输出是,否则输出否或者不停下来。

  当且仅当对于问题都每一个真实例,不确定算法都会在某次执行中返回是的时候,我们说它能够求解这个判定问题。

  如果一个不确定算法在验证阶段的时间效率是多项式级的,我们说它是不确定多项式的类型。

NP类问题是一类可以用不确定多项式算法求解的判定问题,这种问题类型称为不确定多项式类型。

大多数判定问题都属于NP问题。NP问题也包含哈密顿回路问题,旅行商问题,背包问题,划分问题,装箱问题,图的着色问题,整数线性规划问题。停机问题则属于为数很少,一句不属于NP问题的判定问题。

一个NP完全问题是NP中的一个问题,他和该类型中任何其他问题的难度都是一样的,NP中的任何其他问题都能够在多项式的时间内化解为这种问题.

一个判定问题D是NP完全问题,条件是,一它属于NP问题,二NP中的任何问题都能够在多项式时间内化简为D.

上一篇:UVA - 12298 Super Poker II NTT


下一篇:CSS 属性用法备忘录