关于NPcomplete-创新互联

在看论文期间遇到NP complete，在网上查了一些关于他的信息，总结上就是NP=P? ，通俗的说就是“非确定的问题通过穷举法能否得到一种算法，使问题变成确定的（自己理解）”

下面是从网络上得到的相关的说明：

创新互联坚持“要么做到，要么别承诺”的工作理念，服务领域包括：网站制作、做网站、企业官网、英文网站、手机端网站、网站推广等服务，满足客户于互联网时代的息烽网站设计、移动媒体设计的需求，帮助企业找到有效的互联网解决方案。努力成为您成熟可靠的网络建设合作伙伴！

NP COMPLETE
即通常所说的NP（完全）问题，简单的写法，是 NP=P？的问题。NP问题到底是Polynomial，还是Non-Polynomial，尚无定论。不管我们编写程序是否灵巧，判定一个答案是可以很快利用内部知识来验证，还是没有这样的提示而需要花费大量时间来求解，被看作逻辑和计算机科学中最突出的问题之一。它是斯蒂文•考克（Stephen Cook）于1971年陈述的。
NP里面的N，不是Non-Polynomial的N，是Non-Deterministic，P代表Polynomial倒是对的。NP就是Non-deterministic Polynomial的问题，也即是多项式复杂程度的非确定性问题。
什么是非确定性问题呢？有些计算问题是确定性的，比如加减乘除之类，你只要按照公式推导，按部就班一步步来，就可以得到结果。但是，有些问题是无法按部就班直接地计算出来。比如，找大质数的问题。有没有一个公式，你一套公式，就可以一步一步推算出来，下一个质数应该是多少呢？这样的公式是没有的。
这种问题的答案，是无法直接计算得到的，只能通过间接的“猜算”来得到结果。这也就是非确定性问题。而这些问题的通常有个算法，它不能直接告诉你答案是什么，但可以告诉你，某个可能的结果是正确的答案还是错误的。这个可以告诉你“猜算”的答案正确与否的算法，假如可以在多项式时间内算出来，就叫做多项式非确定性问题。而如果这个问题的所有可能答案，都是可以在多项式时间内进行正确与否的验算的话，就叫完全多项式非确定问题。
完全多项式非确定性问题可以用穷举法得到答案，一个个检验下去，最终便能得到结果。但是这样算法的复杂程度，是指数关系，因此计算的时间随着问题的复杂程度成指数的增长，很快便变得不可计算了。
人们发现，所有的完全多项式非确定性问题，都可以转换为一类叫做满足性问题的逻辑运算问题。既然这类问题的所有可能答案，都可以在多项式时间内计算，人们于是就猜想，是否这类问题，存在一个确定性算法，可以在指数时间内，直接算出或是搜寻出正确的答案呢？这就是著名的NP=P？的猜想。

让自己想到了高等数学中的极限的定义，无限的接近，把无限接近的数叫做它的极限，有些相似之处但是又有所不同。

标题名称：关于NPcomplete-创新互联
网页地址：http://cqcxhl.cn/article/csjcep.html