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://cs.stackexchange.com/questions/24264/are-np-complete-languages-closed-under-any-regular-operations

http://stackoverflow.com/questions/26893497/concatenation-of-two-languages-in-np

05-06 18:15