《计算理论_计算复杂性_2016》由会员分享，可在线阅读，更多相关《计算理论_计算复杂性_2016（76页珍藏版）》请在金锄头文库上搜索。
1、教材: 1王 王晓东,计算机算法设计与分析(第4版),电子工业. 2S 唐常杰等译, Sipser著, 计算理论导引, 机械工业. 参考资料: 3C 潘金贵等译, Cormen等著, 算法导论, 机械工业. 4M 黄林鹏等译, Manber著, 算法引论-一种创造性方法, 电子. 5刘 刘汝佳等, 算法艺术与信息学竞赛, 清华大学. 6L Lewis等著, 计算理论基础, 清华大学. 计算理论与 算法分析设计 刘 庆 晖 计算理论 第三部分 计算复杂性 第7章 时间复杂性 1. 时间复杂性 0k1k | k0 的时间复杂性分析 2. 不同模型的运行时间比较 单带与多带 确定与非确定 3. P类
2、与NP类 4. NP完全性及NP完全问题 一. 时间复杂度 时间复杂度定义 0k1k | k0 的时间复杂度分析 时间复杂性 判定器M的运行时间或时间复杂度是f:NN, f(n)是M在所有长为n的输入上运行的最大步数. 若f(n)是M的运行时间, 则称 M在时间f(n)内运行 或 M是f(n)时间图灵机 举例: 大O与小o记法 对于函数f,g:NR+, 记f(n)=O(g(n),若存在c0使得 记f(n)=o(g(n),若 分析算法 讨论语言A = 0k1k | k0 的复杂性: M1=“对输入串w: 1)扫描带,如果在1的右边发现0,则拒绝. 2)如果0和1都在带上,就重复下一步. 3) 扫
3、描带,删除一个0和一个1. 4)如果带上同时没有0和1,就接受.” 时间分析: (1) 2n=O(n), 4) n=O(n), (2) 2n=O(n) + (3) 2n=O(n) (n/2) = O(n2) 所以M1的运行时间是O(n2). 时间复杂性类 定义: 对于函数t:NN, 时间复杂性类 TIME( t(n) ) 定义为: TIME(t(n) = L | 存在O(t(n)时间TM判定L 因为M1是时间O(n2)图灵机, 所以A=0k1k:k0TIME(n2). 是否存在更快的TM判定A呢? 图灵机M2 M2=“对输入串w: 1)扫描带,若1的右边有0,则拒绝. 2)若0,1都在带上,重
4、复以下步骤. 3) 检查带上0,1总数的奇偶性, 若是奇数,就拒绝. 4) 再次扫描带, 第1个0开始,隔1个0删除1个0; 第1个1开始,隔1个1删除1个1. 5)若带上同时没有0和1,则接受. 否则拒绝.” O(n) O(n) O(n) O(n) O(n) log n 总时间: O(nlogn) 0k1k|k0TIME(nlogn) 由图灵机M2知道ATIME(n log n) 有没有更快的图灵机识别A? 对于单带确定图灵机, 由 定理: 时间o(nlogn)的单带图灵机判定的语言 是正则语言. TIME(o(nlogn) 正则语言类 TIME(n) 正则语言类 = TIME(n) = T
5、IME(o(nlogn) 非正则语言 0k1k | k0TIME(o(nlogn) 二. 不同模型的时间复杂度比较 单带与多带 确定与非确定 单带与多带运行时间比较 0k1k | k0 有O(n)时间双带图灵机 M3=“对输入串w: 1) 扫描1带,如果在1的右边发现0,则拒绝. 2) 将1带的1复制到2带上. 3) 每删除一个1带的0就删除一个2带的1. 4) 如果两带上同时没有0和1,就接受.” 定理:设函数t(n)n, 则每个t(n)时间多带TM 和某个O(t2(n)时间单带TM等价. 0k1k|k0的O(n)时间双带图灵机 q0q1 qaq2 NTM的运行时间 定义: 对非确定型判定器
6、N, 其运行时间f(n)是 在所有长为n的输入上, 所有分支的最大步数. . . . f(n) 接受/拒绝 . . . f(n) . . . . . . . . . TMNTM 定理: 设t(n)n, 则每个 时间t(n)NTM 都有一等价的 时间2O(t(n)TM. NTIME(t(n) TIME (2O(t(n) 三. P与NP 多项式时间 运行时间相差多项式可以认为是小的 相差指数可以认为是大的. 例如:n3与2n,对于n=1000. 有关素性测试: Prime= p | p是素数 如何编码? 一进制,二进制,十进制? 典型的指数时间算法来源于蛮力搜索. 有时通过深入理解问题可以避免蛮搜
7、. 2001年Prime被证明存在多项式时间算法. P类 定义:P是单带确定TM在 多项式时间内可判定的问题,即 P = k TIME(nk) P类的重要性在于: 1) 对于所有与单带确定TM等价的模型,P不变. 2) P大致对应于在计算机上实际可解的问题. 研究的核心是一个问题是否属于P类. NP类 NTIME(t(n)=L|L可被O(t(n)时间NTM判定. 定义:NP是单带非确定TM在 多项式时间内可判定的问题,即 NP = k NTIME(nk) EXP = k TIME(2(nk) P NP EXP P EXP 一些P问题 有些问题初看起来不属于P 求最大公因子: 欧几里德算法, 辗
8、转相除法 模p指数运算ab mod p 素性测试 等等 以增加空间复杂性来减小时间复杂性 上下文无关语言 有O(n3)判定器 快速验证 HP = |G是包含从s到t的 哈密顿路径的有向图 CLIQUE=|G是有k团的无向图 目前没有快速算法,但其成员是可以快速验证的. 注意:HP的补可能不是可以快速验证的. 快速验证的特点: 1. 只需要对语言中的串能快速验证. 2. 验证需要借助额外的信息:证书,身份证. NP问题 团:无向图的完全子图(所有节点都有边相连). CLIQUE=|G是有k团的无向图 定理: CLIQUENP. N=“对于输入,这里G是一个图: 1)非确定地选择G中k个节点的子集
9、c. 2)检查G是否包含连接c中节点的所有边. 3)若是,则接受;否则,拒绝.” 哈密顿路径问题HPNP HP=|G是包含从s到t的 哈密顿路径的有向图 P时间内判定HP的NTM: N1=“对于输入: 1)非确定地选G的所有节点的排列p1,pm. 2)若s=p1,t=pm,且对每个i, (pi,pi+1)是G的边, 则接受;否则拒绝.” P与NP P=成员资格可以快速判定的语言类. NP=成员资格可以快速验证的语言类. 显然有 PNP 但是否有 P=NP ? 看起来难以想象, 但是现在没有发现反例. P NP P=NP 当代数学与 理论计算机 共同的难题. NP完全性的定义 SAT是NP完全问
10、题 一些NP完全问题 NP完全性 Cook和Levin于70s证明 NP中某些问题的复杂性与 整个NP类的复杂性相关联, 即: 若这些问题中的任一个找到P时间算法,则P=NP. 这些问题称为NP完全问题. 理论意义:两方面 1)研究P与NP关系可以只关注于一个问题的算法. 2)可由此说明一个问题目前还没有快速算法. 合取范式 布尔变量: 取值为1和0( True, False )的变量. 布尔运算: AND(),OR (),NOT (). 布尔公式. 例: 1 = ( (x) y ) ( x (z) ), 2 = (x) x 称可满足, 若存在布尔变量的0,1赋值使得=1. 不可满足 永真 文
11、字: 变量或变量的非,如x或x. 子句:由连接的若干文字,如x1(x2)x3x4. 合取范式(cnf):由连接的若干子句,如 (x1)x2(x3) (x2(x3)x4x5) (x4)x5) k-cnf (conjunctive normal form) 每个子句的文字数不大于k: 3cnf, 2cnf 可满足问题SAT 可满足性问题: SAT = | 是可满足的布尔公式 二元可满足性问题: 2SAT = | 是可满足的2cnf 三元可满足性问题: 3SAT = | 是可满足的3cnf 二元可满足问题2SATP 1. 当2cnf中有子句是单文字x, 则反复执行(直接)清洗 1.1 由x赋值, 1
12、.2 删去含x的子句, 1.3 删去含x的文字 若清洗过程出现相反单文子子句, 则清洗失败并结束 (x1x2)(x3x2)(x1)(x1x2)(x3x4)(x3x5) (x4x5)(x3x4) (x3x2)(x2)(x3x4)(x3x5) (x4x5)(x3x4) (x3x4)(x3x5) (x4x5)(x3x4) 2. 若无单文字子句, 则任选变量赋真/假值各(赋值)清洗一次 若两次都清洗失败, 则回答不可满足. x3=1 (x5)(x4x5)(x4) (x4)(x4) 失败 x3=0 (x4)(x4x5) (x5) 成功 3. 若成功清洗后有子句剩下, 则继续2. 否则, 回答可满足. 注
13、: 见S习题7.23, 作者给出的答案与清洗算法等价 3SATNP 三元可满足性问题: 3SAT = | 是可满足的3cnf P时间内判定3SAT的NTM: N=“对于输入, 是一个3cnf公式, 1)非确定地选择各变量的赋值T. 2)若在赋值T下 =1, 则接受;否则拒绝.” 第2步在公式长度的多项式时间内运行. 3SATP? 3SAT = | 是可满足的3cnf 清洗算法对3cnf是否有效? 举例对比: (x3x3)(x1x2)(x1x2)(x1x2)(x1x2) (x3x3)(x3x1x2)(x3x1x2)(x3x1x2)(x3x1x2) 后者若按x3=1继续清洗会得到错误结论 3cnf
14、用清洗算法需x3=1和=0都搜索到, 指数时间. 目前还不知道3SAT是否属于P. 多项式时间映射归约与C-L定理 Cook-Levin定理: SATP P=NP. 定义:多项式时间可计算函数f:*. 定义:称A可多项式时间映射归约到B (APB), 若存在多项式时间可计算函数f:*, w*, wA f(w)B. 函数f称为A到B的多项式时间归约. 通俗地说: f 将A的实例编码转换为B的实例编码. Cook-Levin定理: 对任意ANP都有A P SAT. 定理1: 若 A P B, 且 BP, 则 AP. 注: 定理1说明, 若SATP, 则 NP = P . 多项式时间映射归约的作用
15、输入w f f(w) M y/n w*, wA f(w)B. 定理1: 若 A P B, 且 BP, 则 AP. 证明: 设 f:*是A到B的P时间归约, B有P时间判定器M, 则 N=“输入w, 计算M(f(w), 输出M的运行结果” 在多项式时间内判定A. 利用f和B的判定器 构造A的判定器 定理: 3SAT P CLIQUE 3SAT = | 是可满足的3cnf公式 CLIQUE = | G是有k团的无向图 . 证明:设=(a1b1c1)(akbkck),有k个子句. f() = , G有k组节点,每组3个; 同组节点无边相连, 相反标记无边相连. f(x1x1x2)(x1x2x2)(x1x2x2) = x1 x1 x2 x1 x2 x2 x
