【计算复杂性概论】赵瑞清.pdf

【计算复杂性概论】赵瑞清.pdf

计算复杂性概论 赵瑞清 编著 孙宗智 苏豪出做社目录 前言 引言 第一章组合复杂性1布尔函数1计算链和组合机1组合复杂性度量81组合复杂性下界为线性的布尔函数S1 函数集的组合复杂性一些常用函数的组合复杂性S1 渐近界 .第二章算法的计算复杂性和计算模型2算法与它的计算复杂性2确定型图灵机52确定型图灵机与组合机的相似性S2随机存取机RAMRAM机的程序的计算复杂性2.前官 关于计算复杂性,尤其是其中的NP-完全问题,人们认为 是计算机科学理论中最重要的问题,自从1071年S.Co0k提 出P类问题是否等价NP类问题以来,许多著名科学家对这个 向题进行了深入探讨,有的企图证明它们等价,更多的人猜测 并企图证明它们不等价。但迄今为止,人们并没有获得完全 的成功,并且越来越多的迹象表明,这是一个十分困难的问 题,从而带动了许多问题的研究,发展起一个庞大的理论系 统。这些研究无论是对增进人们对P和NP本质的了解,还是 对许多问题的复杂性的解决,都有着重大的意义,这也许是 Cook最初也未预料到的。