计算复杂性理论介绍.ppt

从NP完全性谈起 计算复杂性理论介绍 孙广中，万颖瑜 sungz, 报告内容： “算法”与“好的算法” NP完全性 如何处理NP 完全问题 新的计算模型与希望 例1：可满足性（Satisfiability）问题 布尔变量集合 布尔变量 和 称为文字 子句集合 子句 是一些文字的析取（逻辑或） 真值赋值 给定U和C，是否存在满足C的真值赋值 ？ 可满足：C中所有的子句在 t 下为真 计算复杂度： 例2：货郎担问题 （Traveling salesman problem) 给定n个城市，任意两个城市间有路相 连，一个货郎从一个城市出发，不重复 的遍历所有的城市并回到起点，求一条 路程最短的路径。 加权完全图 ， ， ，求Hamilton圈 ，使得 计算复杂度： 指数灾难：计算量的指数增长 指数灾难能否避免？ SAT问题，货郎担问题，背包问题，图 着色问题，最长路径问题， 是否对于每个问题都有好的算法？ 什么是好的算法？ 什么是算法？ 算法的定义 为实现某个任务而构成的简单指令集 有穷的计算良过程 通过有限多次运算可以决定的过程 正确 直观，非形式 算法的定义 希尔伯特第十问题（1900） 设计一个算法来判断多项式是否有整数根 算法：通过有限多次运算可以决定的过程 Alan Turing & Alonzo Church（1936） 图灵机程序 算法：图灵机程序 形式化的，精确的 图灵机（Turing Machine) 带子可读可写 无限长的带子 读写头可左移右移 有限状态控制器 111 111000000 0BBB1 图灵机（Turing Machine) TM运行由 确定:当前状态为q，所读字符为 s ，读写头不变， ， ，读写头左移一格，s不变， ，读写头右移一格，s不变， 无定义，则停机 Church-Turing论题：凡是可计算的过程都可 用图灵机实现； 其他图灵机模型 “实际的”的图灵机模型 单带图灵机（1TM） 多带图灵机（kTM） 随机存取机（RAM） “实际的” 单位时间内完成的工作量有一个多项式上界 所有“实际的”计算模型多项式时间等价 好的算法多项式时间算法 算法的时间复杂度 指数时间 多项式时间 为什么是多项式而不是其他函数？ 常见的组合算法大致可分以上两类 与计算模型无关性 什么是算法？ 什么是好的算法？ 是否对于每个问题都有好的算法？ P类（Polynomial) 判定问题：只有肯定和否定两种答案 优化问题可以化作判定问题处理 P类 具有多项式时间算法的判定问题形成的计 算复杂性类 猜测TSP（Traveling salesman problem)不属 于P（J.Edmonds 1965） 非确定型算法 不现实的计算 现实中的计算方式都是确定的 解SAT问题的一个非确定型算法 第一步：猜测一个变量的真值赋值； 第二步：检查该赋值是否满足 非确定型算法的计算时间： 各种可能的计算过程的最短时间 非确定型图灵机（NTM) 猜想阶段 验证阶段 有限状态控制器 111 111000000 0BBB1 猜想模块 NTM计算树 计算过程：从根到叶节点的路径 NP类(Nondeterministic Polynomial ) NP问题： 在非确定型图灵机上多项式时间可解的问题 在确定型图灵机上多项式时间可验证的问题 P类包含于NP类中 NP类问题在确定图灵机上指数时间可解 非确定型图灵机和确定型图灵机的计算能力相当 计算难度比较的标准 难易是比较而言的 多项式时间归约（Karp归约 1972) 定义 问题A多项式时间内转化为问题B的特殊情 况，则称A可多项式归约于B，记为 转化时间为多项式 对于A的输入I 的回答与其对应的B的输入 f(I) 一致 NP完全与NP-hard NP完全问题： NP-hard问题： NP完全问题 第一个NP完全问题（Cook定理 1971 ） 可满足性问题是NP完全问题 六个NP完全问题（Karp 1972) 3SAT，3DM，VC，团，HC，划分 更多的NP完全问题 1979年：300多个 1998年：2000多个 现在的估计 如果 ，则指数灾难无法避免 P=?NP （P-NP问题） P=NPP NPC NP 如何处理NP完全问题 实际的问题不会消失 油井勘探问题 移动通讯中的频率分配问题 并行计算 以硬件设备换取时间 存在着很多种并行计算模型 理想模型PRAM可多项式时间解NP完全问 题 实际中效果不好 处理器数目是受限的 现实的代价：通讯，同步， 分布式计算 算法的研究 随机算法 判定问题： 以较大概率得到正确输出 输出正确，但计算时间不定 优化问题：输出解的性能不稳定 以较大概率得到性能好的解 算法的研究 完全算法 利用某些策略减少计算量 分支界限法（Branch and Bound） 最坏情况时间复杂度是指数的 近似算法 不要最优，只求较优 时间复杂度较低 算法的研究 近似算法 局部搜索 遗传算法 模拟退火 TSP问题实验结果 （实验环境：PII450双CPU，256M内存, Turbo Linux 4.0 ） InstanceEAX-h+ILKPattern1 名称 Pcb442507782050778(0)57.0(0.005)2050778(0)13.11(0.10) Att532276862027686(0)36.14(0.01)2027686(0) 51.52(0.026 ) Rat7838806208806(0)26.66(0.01)208806(0) 46.32(0.019 ) Fl1577222492022249(0)589.1 (0.95)2022249(0)97.4(0.035) Pr23923780320 378161(0 ) 624.6(0.94)0378224(0)642.0(1.65) Fl379528772028783(0)1488.2(5.2)028788 (0) 1103.4(14.3 ) 新的计算模型 生物计算 DNA计算机 量子计算 量子计算机 DNA计算 实验处理了7城市Hamilton路径问题 L. Adleman 1994 可以多项式时间解所有的NP问题 Lipton R J 1995 实验可以建立一个非确定型图灵机 Smith W, Schweitzer A. 1995 DNA计算的困难 操作的复杂性 单元操作的时间代价高 规模的限制 处理的问题规模较小 输入输出 纠错的问题 量子计算 量子计算思想的提出 Richard Feynman 1982 量子图灵机模型 David Deutsch 1985 Shor算法（Peter Shor 1994） 多项式时间分解大数质因子 Grover 算法（Grover L. K. 1996） 无序数据库的搜索： 量子计算的困难 操