- 多项式时间可解的问题:如果对于某个确定的常数k，存在一个能在\(O(n^k)\)时间内求解出某具体问题的算法，就说该具体问题是一个多项式时间可解问题。
- 多项式时间内可被验证的问题: 是一个判定问题，答案只有是或否。例如，存在某具体问题，我们猜想该问题有一个可行解x，如果对于某个确定的常数k，存在一个能在\(O(n^k)\)时间内验证x是否是该具体问题可行解的算法，就说该具体问题是一个多项式时间可被验证的问题。
- P问题: 可以在多项式时间内被解决的问题。
- NP问题: 可以在多项式时间内被验证，但是不确定是否可以在多项式时间内找出解。
- NP-Hard问题: 已经有一个很难的问题L’，而L问题比L’更难解决，那么该问题就是NP-Hard问题。NP-Hard问题不确定是否可以在多项式时间内被验证。
- NP-Complete问题: 如果一个问题已经被证明是一个NP-Hard问题，并且可以证明该问题是一个NP问题，那么该问题是NPC问题。
- \(P=NP\): 如果\(P=NP\)成立，那么所有可以在多项式时间内验证的问题也可以在多项式时间内解决。这将意味着验证和求解是等价的，从而所有NP问题都是P问题；如果\(P\ne NP\)，即P问题和NP问题是不同的，那么存在一些问题，虽然解可以在多项式时间内验证，但尚未找到在多项式时间内求解的算法。这意味着有一些问题是相对较难解决的。
- TSP相关问题的复杂性: - 哈密尔顿回路问题(NP): 给定一个无向图，问题是找到一个回路，该回路经过每个顶点一次且仅一次。 - TSP判定版本(NPC): 给定一系列城市和每对城市之间的距离，是否存在经过每一座城市一次并回到起始城市的回路，其长度小于给定的常数K？ - TSP原始版本(NP-hard): 给定一系列城市和每对城市之间的距离，求解经过每一座城市一次并回到起始城市的最短回路。