证明问题Q的NP完整性的两个条件
NP的问题都针对性的是判定性问题。
- Q是NP问题,Nodeterministic Polynomial Decisionable
- Q与一个一直的NPC问题一样难,关键是找到一个多项式规约函数。
库克定理的内容
SAT问题属于NP-Complete问题。SAT是第一个被证明的NP完整性问题。往后的NPC问题都是在其 基础上证明出来的。下图是NPC问题的证明历史脉络(存在不同的版本)。
与我们的联系
如果能证明一个问题是NPC问题,那么就能说明他很难解,基本上不存在着多项式时间解法,只能靠暴力破解的方式等来进行解决。 所以不用费力的去找快速的准确解,只能进行近似求解,Approximation Algorithm,然后使得解的精度尽可能近似于最优解。
近似解法的几个衡量标准
- 求解的时间要尽可能快,线性或者多项式时间。
- 近似程度 Approximation Ratio要小。