大家知道问题复杂度NP么?


今天楼主在看一篇论文的时候看到NP就懵了,从来不知道什么是NP。


找了半天,终于找到了答案:

NP:非定常多项式(non-deterministic polynomial,缩写NP)时间复杂性类,或称非确定性多项式时间复杂性类,包含了可以在多项式时间内,对一个判定性算法问题的实例,一个给定的解是否正确的算法问题。NP是计算复杂性理论中最重要的复杂性类之一。它包含复杂性类P,即在多项式时间内可以验证一个算法问题的实例是否有解的算法问题的集合;同时,它也包含NP完全问题,即在NP中“最难”的问题。计算复杂性理论的中心问题,P/NP问题即是判断对任意的NP完全问题,是否有有效的算法,或者NP与P是否相等。


那什么又是NP完全问题呢?又找到了一段解释:
NP完全问题,是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。

举个例子,再来理解一下:

我们不知道81785036517是否为素数,但是要确定277877是否为81785036517因子,我们可以直接拿去除。针对277877来验证8178503651是否为质数的动作可在多项式时间内完成,故针对某可能解来验证某数是否为质数的问题是一个NP问题。


我对NP只理解了一点点,希望大侠指教~