非多项式时间复杂度及NP问题

O(a^n)和O(n!)型复杂度，它是非多项式级的。与非多项式时间复杂度相关的问题叫：非确定性多项式(non-deterministic polynomial  NP)

NP: 不能在多项式时间内解决或不确定能不能在多项式时间内解决，但能在多项式时间验证的问题,P问题是NP问题的一个子类

NPC:非确定性多项式完全问题则是一类目前大家认为没有多项式算法去解决的问题，是NP问题中最难的问题，但是如果你给出了这类问题的一个答案，我可以在多项式时间内验证给出的答案是否正确

NP hard：非确定性多项式困难问题指的是至少和NP完全问题一样难的问题。注意，NP-困难问题有可能比NP完全问题难，但却不会比它容易。（我的理解是它与NPC的区别或者判断依据就是如果给出问题的一个解，可能不能在多项式时间验证）

它们之间的关系：NP完全问题是NP问题的一个子类，它是NP问题中最难的一类问题。NP-困难问题和NP-完全问题有交集，但并不同，它还包含一类比NP完全问题更难的问题

例子：

NP问题：

著名的推销员旅行问题（Travel Saleman Problem orTSP）：假设一个推销员需要从香港出发，经过广州，北京，上海，      …，等 n 个城市， 最后返回香港。任意两个城市之间都有飞机直达，但票价不等。假设公司只给报销 C 元钱，问是否存在一个行程安排，使得他能遍历所有城市，而且总的路费小于 C

NP hard问题：

输出n个元素的全排列