1.图灵停机问题:无论在多长时间内都无法被任何一台计算机解决
问题描述:问题为H,H的输入数据为P(P是一段程序(程序也是一串字符串数据)),判定P在输入w下是否能够最终停止
H(P(w))=0 若P在输入w下可停机
-1 若P在输入w下死循环(H的输出为状态)
分析:假设问题H可解,则构造一个过程K(P),输入为一段程序,K的输出结果依赖于H(P(P))的结果
procedure K(input P):
if (H(P(P))==0) 死循环
else if (H(P(P))==-1) return 0;
则对K(K):若K(K)死循环,则H(K(K))=0,K(K)应当可停机
若K(K)停机,则H(K(K))=-1,K(K)本应为死循环
出现矛盾
//真是绕……这段改了三遍才懂
2.一些问题实例
1)在有向图G=(V,E)中,在O(VE)时间内从单一源顶点开始找到最短路径
相关NPC:确定一个图在给定数量的边中是否包含一条简单路径
2)可以在O(E)时间确定一个图是否有Eular回路(恰好经过每一条边的回路)(22-3),事实上,可以在O(E)时间遍历欧拉回路的各条边
相关NPC:确定一个有向图是否包含哈密顿圈(恰好经过每一个顶点一次的简单回路)
3)k-CNF:k合取范式,用and连接若干个or子句,且每个子句恰有k个bool变量或其否定
多项式时间判断2-CNF的可满足性(是否存在一组合法赋值):多项式时间
3-CNF的可满足性:NPC
3.P,NP,NPC problems
P类:可在O(n^k)时间内解决
NP类:可在多项式时间内验证(给定一组赋值)
显然P类问题也是NP问题
NPC问题的集合运算的封闭性讨论:
http://stackoverflow.com/questions/26893497/concatenation-of-two-languages-in-np