S10-NP难度和NP完全问题
- 易解问题与难解问题
- 易解问题的举例和难解问题的分类
- P问题-非正式与正式定义、判定问题
- 最优化问题可转化为判定问题
- NP问题-不确定算法
- 不确定算法
- P与NP关系——约化/规约、NP完全问题、Cook定理、NP难问题
- 问题间的联系-归化/规约
- 约化举例
- NP-完全问题
- NP-Hard问题
- NP-C与NP-Hard问题的关系
- SAT问题
- SAT的不确定算法
- COOK定理
- P、NP、NP-C、NP-Hard的关系图
易解问题与难解问题
易解问题的定义:一个问题能够在多项式时间内求解。
难解问题的定义:一个问题不能够在多项式时间内求解。
选择使用多项式时间来确定是否为难处理问题的原因:
易解问题的举例和难解问题的分类
易解的问题:排序问题、最优二分检索树问题、单源点最短路径问题等。
难解问题分为两类:
- 一类是不可计算的,即根本不存在求解的算法,如“任意的整系数多元代数方程是否有整数解”(著名的希尔伯特第十问题)
- 另一类是解法的时间限度为非多项式时间内,如在数理逻辑、组合游戏等领域内,已经找到一些问题,它们都有算法解决,但至少需要指数时间或指数空间,这些也都是难解的。
难办的是,人们发现一大批问题(包括货郎担问题、背包问题等)既没有找到它们的多项式时间算法
(目前没找到易解的算法),也没能证明它们是难解的
。
P问题-非正式与正式定义、判定问题
非正式定义:我们可以把那些能够在多项式时间内求解的问题,当作计算机科学家所说的P集合。
正式定义:所有多项式时间内可解的判定问题
所构成的问题集合,称为“P类”问题;一个判定问题是易解的,当且仅当它属于P类问题
最优化问题可转化为判定问题
如果判定问题不能在多项式时间内求解,那么与它相应的最优化问题也不能在多项式时间内求解。
NP问题-不确定算法
NP问题的定义:NP是所有可在多项式时间内用不确定算法验证
的判定问题的集合。
不确定算法
一个不确定算法是一个两阶段的过程,
- 非确定(猜测)阶段:生成一个任意串S,把它当做给定实例l的一个候选解;
- 确定(验证)阶段:确定算法把l和S都作为它的输入,如果S的确是l的一个解,就输出“是”。
P与NP关系——约化/规约、NP完全问题、Cook定理、NP难问题
问题间的联系-归化/规约
约化举例
NP-完全问题
定义:
- 它是一个NP问题
- 所有的NP问题都可以归约到它
NP-Hard问题
定义:
- 所有的NP问题都可以归约到它
NP-C与NP-Hard问题的关系
SAT问题
SAT问题——可满足性问题,为第一个被证明为NPC的问题,也称之为NP-完全问腿的种子
定义:
SAT的不确定算法
COOK定理
若证得SAT问题有多项式时间内的确定算法,就能证明P=NP
P、NP、NP-C、NP-Hard的关系图
P问题一定包含于NP-C问题