P, NP, NPC

concepts

• P
• NP
• NPC
• NP-hardness

P

P: can be solved in polynomial time

NP

NP问题是指可以在多项式的时间里验证一个解的问题。NP问题的另一个定义是，可以在多项 式的时间里猜出一个解的问题。

在这个题中，找一个解很困难，但验证一个解很容易。

验证一个解只需要O(n)的时间复杂度，也就是说我可以花O(n)的时间把我猜的路径的长度加出来。

之所以要定义NP问题，是因为通常只有NP问题才可能找到多项式的算法。

P 属于 NP, 人民相信P不等于NP

NPC

NP complete

• Hamilton path problem
• Travelling salesman problem

约化 Reducibility

一个问题A可以约化为问题B的含义即是，可以用问题B的解法解决问题A，或者说，问题A可 以“变成”问题B。

一元一次方程可以约化为一元二次方程。

同样地，我们可以说，Hamilton回路可以约化为TSP问题(Travelling Salesman Problem， 旅行商问题)：在Hamilton回路问题中，两点相连即这两点距离为0，两点不直接相连则令 其距离为1，于是问题转化为在TSP问题中，是否存在一条长为0的路径。

约化有传递性

what's NPC

NPC问题的定义非常简单。同时满足下面两个条件的问题就是NPC问题。

• 首先，它得是一个NP问题；
• 然后，所有的NP问题都可以约化到它。

既然所有的NP问题都能约化成NPC问题，那么只要任意一个NPC问题找到了一个多项式的算法，那么所有的NP问题都能用这个算法解决了，NP也就等于P 了。因此，给NPC找一个多项式算法太不可思议了。因此，前文才说，“正是NPC问题的存在，使人们相信P≠NP”。我们可以就此直观地理解，NPC问题目前没有多项式的有效算法，只能用指数级甚至阶乘级复杂度的搜索。