p,np,np难问题

文章目录1.预备知识1.1多项式1.3约化1.4Hamilton回路2.p类问题polynominal多项式2.1定义一个可以在多项式时间复杂度内解决的问题。2.2举例n个数的排序问题不超过O(n2)3.np问题Nondeterministic polynominal非确定多项式3.1定义4.np难问题4.1定义4.2注意4.3举例1.预备知识1.1多项式1.3约化一个问题A可以约化为B的含义是可以用问题B的解法解决问题A。例如求解一个一元一次方程A和求解一个一元二次方程B你若会求解B你一定会求解A。那么我们说A可以约化为B。可以理解为问题约化后会变难。1.4Hamilton回路从图中的一个顶点出发沿着边行走经过图的每个顶点且每个顶点仅访问一次之后再回到起始点的一条路径。2.p类问题polynominal多项式2.1定义一个可以在多项式时间复杂度内解决的问题。2.2举例n个数的排序问题不超过O(n2)为什么我们要研究这个呢为什么以多项式为标准而不是其他的因为计算机处理的数据量是非常大的想象一下当计算机处理的数据达到100万个的时候时间复杂度为O(n2)和O(2n)的算法所需的运行次数是天文之数指数级的可能运行好几天都没法完成任务。但多项式级别的时间是可以接受的。所以我们也只在乎一个问题是否存在多项式算法而一个时间复杂度比多项式还要复杂的算法研究起来是几乎没有意义的。3.np问题Nondeterministic polynominal非确定多项式3.1定义可以在多项式的时间里验证一个解的问题即给出一个答案可以很快地在多项式时间内验证这个答案是对的还是错的但是不一定能在多项式时间内求出正确的解P类问题是np问题的子集4.np难问题4.1定义任意np问题可以在多项式时间内约化成该问题即为了解决np问题A先将问题A约化为另一个问题B解决问题B同时也间接解决了问题A问题B就是一个np难问题4.2注意np难问题并不完全包含np类问题因为一个问题约化后会变得更难就不一定还能在多项式时间内验证答案。4.3举例旅行商求最短回路设一个推销员需要从香港出发经过广州、北京、上海、…等 n 个城市最后返回香港。任意两个城市之间都有飞机直达但双向的票价不等。求总路程最少的行程安排。分析想要知道所有方案中花费最少的必须检查所有可能的旅行安排才能找到即(n-1)!种方案很显然这不是P问题。给出任意一个行程安排你能算出它的总路程但无法在多项式时间内验证这条路径是否是最短路。所以不是NP问题。而之前提出的Hamilton回路问题可以约化到这个问题上。即如果我能解决旅行商问题那么说明我能解决如何找到Hamilton回路。因此这个问题是NP难问题。