顶部
  1. 首页
  2. 图书产品
  3. 计算复杂性导论(变更封面)
收藏

计算复杂性导论(变更封面)

作者：
堵丁柱、葛可一、王杰
定价：
53.00元
ISBN：
978-7-04-011307-5
版面字数：
0千字
开本：
16开
全书页数：
378页
装帧形式：
精装
重点项目：
暂无
出版时间：
2008-10-20
物料号：
11307-A0
读者对象：
学术著作
一级分类：
自然科学
二级分类：
数学与统计

计算复杂性理论是用数学方法研究使用数位计算机解决各种算法问题困难度的理论。本书对计算机科学中这一重要理论做了全面的介绍。其内容包含基本理论，如计算模型NP-完全性，以及较深入的课题，如线路复杂性、概率复杂性和交互证明系统等。此外，本书还包括了复杂性理论近年来两个较重大的突破，即概率可验证明及其在近似算法上的应用和平均NP-完全理论。本书中所有结果均有严格的数学证明，在每章后配有相关练习题。

本书可用作计算机专业、计算数学专业的计算机理论课程的教材，也是有关研究人员不可或缺的参考书。

  • 第一章　计算模型
    • 1.1　符号行，编码和布尔函数
    • 1.2　确定型图灵机
    • 1.3　非确定型图灵机
    • 练习题
  • 第二章　计算复杂性类
    • 2.1　时间与空间
    • 2.2　通用图灵机
    • 2.3　对角线方法
    • 2.4　模拟
    • 练习题
  • 第三章　NP-完全问题
    • 3.1　NP
    • 3.2　Cook定理
    • 3.3　NP-完全问题的例子
    • 3.4　多项式时间图灵归约
    • 练习题
  • 第四章　多项式时间分层和多项式空间
    • 4.1　非确定型带神喻图灵机
    • 4.2　多项式时间分层
    • 4.3　PH中的完全问题
    • 4.4　交替图灵机
    • 4.5　PSPACE-完全问题
    • 练习题
  • 第五章　线路复杂性
    • 5.1　布尔线路
    • 5.2　单调递增函数与单调线路
    • 5.3　奇偶性函数与深度有界线路
    • 5.4　多项式规模布尔线路
    • 练习题
  • 第六章　NP类的结构
    • 6.1　NP中的非完全问题
    • 6.2　单向函数及其在密码学中的应用
    • 6.3　NC
    • 6.4　P-完全性
    • 6.5　NP-完全问题的密度
    • 6.6　EXP-完全问题的密度
    • 练习题
  • 第七章　概率机与复杂性类
    • 7.1　随机算法
    • 7.2　概率图灵机及其时间复杂性
    • 7.3　带有界误差的概率机
    • 7.4　BPP，NP和多项式时间分层
    • 练习题
  • 第八章　计数复杂性
    • 8.1　计数类#P
    • 8.2　#P-完全问题
    • 8.3　⊕P和多项式时间分层
    • 8.4　＃P和多项式时间分层
    • 练习题
  • 第九章　交互证明系统
    • 9.1　例子与定义
    • 9.2　亚瑟-默林证明系统
    • 9.3　AM分层与多项式时间分层
    • 9.4　IP与AM
    • 9.5　IP与PSPACE
    • 练习题
  • 第十章　概率可验证明
    • 10.1 PCP的定义
    • 10.2　NEXPPOLY的PCF特征
      • 10.2.1　主要证明
      • 10.2.2　多重线性测试系统
      • 10.2.3　和检验系统
    • 10.3 NF的PCP特征
      • 10.3.1　使用O(logn)个随机数码的PCP系统
      • 10.3.2　低阶测试系统
      • 10.3.3　两个PCP系统的复合
      • 10.3.4　阅读常数多神喻数码的PCP系统
    • 练习题
  • 第十一章　近似解的复杂性
    • 11.1　NP-完全优化问题
    • 11.2　PCT和不可近似性
    • 11.3　优化问题的归约
    • 11.4　难近似的优化问题
    • 练习题
  • 第十二章　平均NP-完全性理论
    • 12.1　平均易解性
    • 12.2　多项式时间归约
    • 12.3　P-分布
    • 12.4　平均NP-完全问题
    • 12.5　扁平分布与随机归约
    • 12.6　扁平分布下的完全问题
    • 12.7　可抽样分布
    • 练习题
  • 参考文献
  • 名词索引（汉英对照）
  • Paeface
  • Chapter 1 Models of Computation
    • 1.1 strings,coding and Boolean Functions
    • 1.2 Deterministic Turing Machines
    • 1.3 Nondeterministic Turing Machines
    • Exercises
  • Chapter 2 Complexity Classes
    • 2.1 Time and Space
    • 2.2 Universal Turing Machines
    • 2.3 Diagonalization
    • 2.4 Simulation
    • Exercises
  • Chapter 3 NP-completeness
    • 3.1 NP
    • 3.2 Cook's Theorem
    • 3.3　Examples of NP-Complete Problems
    • 3.4 Polynomial-Time Turing Reducibility
    • Exercises
  • Chapter 4 Polynomial-Time Hierarchy and Polynomial Space
    • 4.1 Nondeterministic Oracle Turing Machines
    • 4.2 Polynomial-Time Hierarchy
    • 4.3 Complete Problems in PII
    • 4.4 Alternating Turing Machines
    • 4.5 PSPACE-Complete Problems
    • Exercises
  • Chapter 5 Circuit Complexity
    • 5.1 Bonlaan Circuits
    • 5.2 Monotone Increasing Functions and Monotone Circuits
    • 5.3 Parity Function and Constant Depth Circuits
    • 5.4 Polynomial-Size Boolean Circuits
    • Exercises
  • Chapter 6 Structure of NP
    • 6.1 Incomplete Problems in NP
    • 6.2 One-Way Functions and Cryptography
    • 6.3 NC
    • 6.4 P-Completeness
    • 6.5 Density of NP-Complete Sets
    • 6.6 Density of EXP-Complete Sets
    • Exercises
  • Chapter 7 Probabilistic Machines and Complexity Classes
    • 7.1 Randomized Algorithms
    • 7.2 Probabilistic Turing Machines and Time Complexity
    • 7.3 Probabilistic Machines with Bounded Errors
    • 7.4 PPP,NP and the Polynomial-Time Hierarchy
    • Exeicises
  • Chapter 8 Complexity of Counting
    • 8.1 Counting Class #P
    • 8.2 #P-Complete Problems
    • 8.3 ⊕P and the Polynomial-Time Hierarchy
    • 8.4 #P and the Polynomial-Time Hierarchy
    • Exeicises
  • Chapter 9 Interactive Proof Systems
    • 9.1 Examples and Definitions
    • 9.2 Arthur-Merlin Proof Systems
    • 9.3 AM Hierarchy Versus the Polynomial-Time Hierarchy
    • 9.4 IP and AM
    • 9.5 IP and PSPACE
    • Exercises
  • Chapter 10 Probabilistically Checkable Proofs
    • 10.1 Definition of PCP
    • 10.2 PCP Characterization of NEXPPPOLY
      • 10.2.1 Main Proof
      • 10.2.2 Multilinearity Test System
      • 10.2.3 Sum Check System
    • 10.3 PCP Characterization of NP
      • 10.3.1 PCP System Using O(logn)Random Bits
      • 10.3.2 Low-Degree Test System
      • 10.3.3 Composition of Two PCP Systems
      • 10.3.4 PCP System Reading a Constant Number of Oracle Bits
    • Exercises
  • Chapter 11 Complexity of Approximation Problems
    • 11.1 NP-Complete Optimization Problems
    • 11.2 PCP and Nonapproximability
    • 11.3 Reductions Among Optimization Problems
    • 11.4 Hard-to-Approximate Optimization Problems
    • Exercises
  • Chapter 12　Theory of Average-Case NP-Completeness
    • 12.1 Easiness on Average
    • 12.2 Polynomial-Time Reducibility
    • 12.3 p-Distributions
    • 12.4 Average-Case NP-Complete Problems
    • 12.5 Flat Distributions and Random Reductions
    • 12.6 Complete Problems Under Flat Distributions
    • 12.7 Samplable Distributions
    • Exercises
  • References
  • Index

相关图书

代数K-理论导论（影印版）

Charles A. Weibel

￥269.00 收藏

代数学引论(第三卷)基本结构(第2版)(变更封面)

A. N. 柯斯特利金 著，郭文彬 译

￥49.00 收藏

偏微分方程习题集(第2版)(变更封面)

А. С. 沙玛耶夫 主编，郭思旭 译

￥29.00 收藏

光滑遍历理论导论（影印版）

Luis Barreira,Yakov Pesin

￥135.00 收藏

函数论与泛函分析初步(第7版)(变更封面)

А. Н. 柯尔莫戈洛夫等

￥69.00 收藏

反演问题的计算方法及其应用

王彦飞 著

￥59.00 收藏

复分析导论(第一卷)(第4版)

[俄] Б. В. 沙巴特 著，胥鸣伟、李振宇 译

￥59.00 收藏

复分析导论(第一卷)单复变函数(第4版)

胥鸣伟 李振宇

￥46.00 收藏

复分析导论(第二卷)多复变函数(第4版)

[俄] Б. В. 沙巴特

￥69.00 收藏

复分析导论(第二卷)多复变函数(第4版)

“[俄] Б. В. 沙巴特 著

￥48.00 收藏

复杂性内在逻辑：从数学到可持续世界(英文版) Grammar of Complexity：From Mathematics to a Sustainable

Dimitri Volchenkov

￥99.00 收藏

实函数导论（第四版）（影印版）

Ralph P. Boas，Revised and updated by Harold P. Boas

￥135.00 收藏

微分几何与拓扑学简明教程(变更封面)

[俄] А. С. 米先柯 А. Т. 福明柯

￥49.00 收藏

控制论中的矩阵计算

徐树方

￥59.00 收藏

数学哲学导论

Stephan Körner 著，胡俊美 译

￥79.00 收藏