计算复杂性(现代方法)/计算机科学丛书

基本信息

目录：

出版者的话
译者序
译者简介
前言
致谢
引言
第0章记号约定
**部分基本复杂性类
**章计算模型——为什么模型选择无关紧要
第2章NP和NP完全性
第3章对角线方法
第4章空间复杂性
第5章多项式分层和交错
第6章布尔线路
第7章随机计算
第8章交互式证明
第9章密码学
**0章量子计算
**1章PCP定理和近似难度简介
第二部分具体计算模型的下界
**2章判定树
**3章通信复杂性
习题
**4章线路下界：复杂性理论的滑铁卢
**5章证明复杂性
**6章代数计算模型
第三部分**专题
**7章计数复杂性
**8章平均复杂性:勒维定理
**9章难度放大和纠错码
第20章去随机化
第21章伪随机构造:扩张图和提取器
第22章PCP定理的证明和傅里叶变换技术
第23章为什么线路下界如此困难
附录
部分习题的提示
参考文献
术语索引
复杂性类索引

......

精 彩 页：

内容提要：

桑杰夫·阿罗拉、博阿兹·巴拉克编写的《计算\复杂性(现代方法)》系统地介绍计算复杂性理论的经\典结果和近30年来取得的新成果，旨在帮助读者了解\和掌握复杂性理论中的基本结果、思维方法、主要工\具、研究前沿和待决问题。本书分为三部分。**部\分（**～11章）较宽泛地介绍了复杂性理论，包括\复杂性理论的经典结果和一些现代专题。第二部分（\**2～16章）讨论了各种具体计算模型上的计算复杂\性下界。第三部分（**7～23章）主要是1980年以后\人们在复杂性理论方面获得的进展，内容包括计数复\杂性、平均复杂性、难度放大、去随机化和伪随机性\、PCP定理的证明以及自然证明。本书内容丰富，结\构灵活，语言流畅，是从事计算复杂性理论及相关领\域的研究人员必不可少的参考书，非常适合作为打算\进入该研究领域的研究生、博士生快速接触研究前沿\的参考资料，还非常适合作为普通高校计算机科学与\技术、数学专业本科生、研究生相关课程的教材，其\中的**专题还可以作为博士生相关讨论班的素材。
    

......

作者简介：

\骆吉洲，男，1975年生，博士，副教授。2006年5月毕业于哈尔滨工业大学计算机科学与技术学院软件与理论专业，获工学博士学位。1999年、2001年在哈尔滨工业大学数学系基础数学专业分别获得理学学士学位和理学硕士学位。现就职于哈尔滨工业大学计算机科学与技术学院海量数据计算研究中心，讲授“算法设计与分析”“数学建模”“编译原理”等课程。出版教材《算法设计与分析》一部，出版译著《图论导引》一部。近年来一直从事生物信息学、压缩数据库技术、传感器网络、算法理论等领域的研究。主持和参加多项**自然基金、863计划、973项目、国防预研等项目等多项；20C11年9月至2003年5月参加“计算机机群并行数据库系统”的研制，该项目获得了2004年度**科学技术进步二等奖。近年来发表30余篇论文。\桑杰夫·阿罗拉(SanJeev Arora)普林斯顿大学计算机科学系教授，在概率可验证明和NP一难问题的可近似性方面取得了基础性的研究成果。他发起创办了“计算难解性问题中心”，该项目由**科学基金资助。\博阿兹·巴拉克(Boaz Barak)现为哈佛大学计算机科学系教授，哈佛大学工学院计算理论研究组成员．同时还是微软新英格兰研究院首席研究员，之前是普林斯顿大学计算机科学系副教授。他在计算复杂性和密码学方面，特别是“非黑盒”技术方面，取得了基础性的研究成果。