NP-hard是什么意思

P：能够以多项式时间被求解的问题称为P-问题。比如说O(n),O(n^5)，这都是多项式时间。

举个例子，给n个数，找出其中所有的偶数。这个就是P-问题。

NP：首先NP-问题不能以多项式的时间求解；并且，如果我们假设找到了一个答案，这个答案可以以多项式的时间检验该答案是否正确。

比如说，我们要找出所有(1,2,3)的置换，并且第一个元素小于第二个元素。这里一共有3!=3*2*1=6个置换，(1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1)，符合第一个元素小于第二个元素的置换有3个。如果是(1,2,...,n)的置换，我们则需要至少O(n!)的时间来求解，这是大于多项式时间的。再者，如果给出任意一个备选答案，比如(5,2,1,4,3)，我们只需要花多项式的时间（这里是O(n)时间）来检查这个备选答案是不是真的是一个置换并且第一个元素小于第二个元素。

NP-hard：首如果一个问题通过一些步骤能够化简为一个NP问题，那么这个问题就是NP-hard问题。换句话说，至少是NP的问题称之为NP-hard问题。

著名的NP-hard例子就是旅行商问题。假设有n个城市，找出一条每个城市都访问一次且仅访问一次的最短路线。