首先要知道两个概念：多项式、时间复杂度
我们为什么要研究这个问题呢？当计算机处理的数据达到100万个的时候，时间复杂度为:O(n^2)和O(e^n)的算法，所需要的运行次数是天壤之别的，所以我们需要研究一个问题是否存在多项式时间算法。而我们也只在乎一个问题是否存在多项式算法，因为一个时间复杂度比多项式算法还要复杂的算法研究起来是没有任何实际意义的。
p问题：可以在多项式的时间内解决的问题；
NP问题：可以在多项式的时间里验证的问题；
P类问题是NP问题的子集，因为存在多项式时间解决的算法，总能在多项式时间内验证它。
验证，就是不知道这个问题是不是存在多项式时间内的算法，所以叫做非确定性，但是我们可以在多项式的时间内验证并得到这个问题的一个正确解。例如旅行商问题就是典型的NP问题，我们能在多项式时间内验证并得到问题的正确解，却不知道该问题是否存在一个多项式时间的算法，每次都能解决它。
这就引出了一个问题NP问题=P问题？
也就是说 ，是否所有能在多项式时间内验证得出正确解的问题，都是具有多项式时间算法的问题？
NPC问题（NP完全问题）：如果所有的NP问题都能在多项式时间内转化为它，则称该NP问题是NPC问题。是NP问题的一个子集，且其中的每个问题均能由NP中的任何问题在多项式的时间内转化而成。
NP难问题(NP-hard)：通俗的来说是其解的正确性能够“很容易检查”的问题，这里的“很容易检查”指的是存在一个多项式检查算法。相应的，若NP中所有问题到某一个是图灵可归约的，则该问题为NP难问题。所有的NPC问题都可以在多项式时间内转化为它，我们就叫它为NPH问题。
NP是指非确定性多项式，所谓的非确定性是指，可用一定数量的运算去解决多项式时间内可以解决的问题。
为了解决这些问题，想出了很多办法，其中之一就是问题的约化，就是可以用问题B的算法来解决问题A，我们就说问题A可以约化成问题B。不断的约化下去，会发现一定存在一个最大的问题，而我们只需要解决了这个问题，其他所有的问题就都解决的，这就是NPC问题。
迄今为止，更倾向于接受NP完全问题和NP难问题不存在有效算法这一猜想，认为这类问题的大型实例不能用精确算法求解，必须寻求这类问题的有效的近似算法。
旅行商问题、子集和问题、Hamilton回路问题、最大团问题
blog.csdn.net/databatman/article/details/49304295
网友评论