Algorithm time complexity rank:

比多项式时间更慢是不能接受的。

P 问题

一个规模为n的问题，如果可以在n的多项式时间内解决，就是是P问题。(算法一定会在多项式时间停止)

NP (Non-deterministic Polynomial) 问题

可以在多项式的时间里验证一个解的问题。

TSP (Traveling Salesman Problem) 旅行推销商问题, 枚举 O(n!)：

• 推销商有N个目的地
• 需要访问所有城市一次，不能重复
• 每两个城市都是连接的

NP complete 和 NP-Hard 问题

如果所有的NP问题都能多项式时间内归约 (转化) 到问题X (X的复杂度大于等于原NP问题)，那么X就是一个NP-Hard问题，如果X也是NP的，称X是NP complete的，否则X就只能是NP-Hard。