常见的NP类问题

NP问题是指可以在多项式的时间里验证一个解的问题。所有的NP问题都可以用多项式时间划归
到他们中的一个。所以显然NP完全的问题具有可以在多项式时间内求解,当且仅当所有的其他的NP-完全问题也可以在多项式时间内求解。
NP完全问题(NP-C问题),是世界七大数学难题之一。 NP的英文全称是Non-deterministic Polynomial的问题,即多项式复杂程度的非确定性问题。简单的写法是 NP=P?,问题就在这个问号上,到底是NP等于P,还是NP不等于P。

著名的NP问题。
1.图着色问题
2.哈密顿回路问题:天文学家哈密顿(William Rowan Hamilton) 提出,在一个有多个城市的地图网络中, 寻找一条从给定的起点到给定的终点沿途恰好经过所有其他城市一次的路径。这个问题和著名的过桥问题的不同之处在于,某些城市之间的旅行不一定是双向的。比如A→B,但B→A是不允许的。换一种说法,对于一个给定的网络,确定起点和终点后,如果存在一条路径,穿过这个网络,我们就说这个网络存在哈密顿路径。哈密顿路径问题在上世纪七十年代初,终于被证明是“NP完备”的。据说具有这样性质的问题,难于找到一个有效的算法。实际上对于某些顶点数不到100的网络,利用现有最好的算法和计算机也需要很长的时间(可能要几百年之久)才能确定其是否存在一条这样的路径。
3.TSP问题:旅行商问题,即TSP问题(Traveling Salesman Problem)是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市,他必须选择所要走的路径,路经的限制是每个城市只能拜访一次,而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。
4.图灵停机问题

发表评论