算法课堂笔记14—NP-COMPLETENESS

今天的算法课接着上一节,说的是NP问题。

1.关于什么是P和NP问题

所谓P问题是指所有能在多项式复杂度解决的问题,比如排序算法,n*n复杂度解决问题。而对于有些问题,目前可能没有多项式复杂度的解决方案,但是如果你给我一个解决方案,我可以在多项式时间内验证该算法是否正确,那么这类问题便是NP问题。P属于NP。这是很明显的,因为他们都是在多项式复杂度内去解决问题,区别在于NP只判断是和否。

2.NP-hardness和NP-completeness

NP-hard Problem:对于这一类问题,用一句话概括他们的特征就是“at least as hard as the hardest problems in NP Problem”, 就是NP-hard问题至少和NP问题一样难。

NP-Complete Problem:对于这一类问题,他们满足两个性质,一个就是在polynomial时间内可以验证一个candidate answer是不是真正的解,另一个性质就是我们可以把任何一个NP问题在polynomial的时间内把他的input转化,使之成为一个NP-complete问题(即规约)。NP-Complete Problem问题可以互相转换 (在多项式时间内),只要其中一个问题可以在多项式时间内解决,那么其他问题也都将可以在多项式时间内解决。

发现了一篇不错的博文来解释这个问题:P问题、NP问题、NPC问题的概念及实例证明

上一篇:redis递减,过期返回值


下一篇:字符串匹配-KMP