- 重要概念:
- 多项式时间可解的问题: 如果对于某个确定的常数k，存在一个能在\(O(n^k)\)时间内求解出某具体问题的算法，就说该具体问题是一个多项式时间可解问题
- 多项式时间内可被验证的问题: 对于某具体问题，猜想该问题有一个可行解x，如果对于某个确定的常数k，存在一个能在\(O(n^k)\)时间内验证x是否是该具体问题可行解的算法
- P问题: 可以在多项式时间内被解决的问题
- NP问题: 可以在多项式时间内被验证的问题，但是不确定是否可以在多项式时间内找出解【P问题必然是NP问题】
- NP-Hard问题: 若所有的NP问题都能多项式时间内归约(可以理解为转化)到问题X(X的复杂度大于等于原NP问题)，那么X就是一个NP-Hard问题【NP-Hard问题不确定是否可以在多项式时间内被验证】
- NP-Complete问题: 如果一个问题已经被证明是一个NP-Hard问题，并且可以证明该问题是一个NP问题，那么该问题是NPC问题[]
- \(P=NP\):
- 如果\(P=NP\)成立，那么所有可以在多项式时间内验证的问题也可以在多项式时间内解决 => 这将意味着验证和求解是等价的，从而所有NP问题都是P问题
- 如果\(P\ne NP\)，即P问题和NP问题是不同的，那么存在一些问题，虽然解可以在多项式时间内验证，但尚未找到在多项式时间内求解的算法 => 这意味着有一些问题是相对较难解决的