计算复杂性的现代方法

图书标准信息

• 作者 [美]阿罗拉 著
• 出版社 世界图书出版公司
• 出版时间 2012-03
• 版次 1
• ISBN 9787510042867
• 定价 99.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 579页
• 正文语种 英语

【内容简介】

《计算复杂性的现代方法》是一部将所有有关复杂度知识理论集于一体的教程。将最新进展和经典结果结合起来，是一部很难得的研究生入门级教程。既是相关科研人员的一部很好的参考书，也是自学人员很难得的一本很好自学教程。本书一开始引入该领域的最基本知识，然后逐步深入，介绍更多深层次的结果，每章末都附有练习。对复杂度感兴趣的人士，物理学家，数学家以及科研人员这本书都是相当受益。

【目录】

AboutthisbOok
Acknowledgments
Introduction
0Notationalconventions

PARTONE:BASICCOMPLEXITYCLASSES
1Thecomputationalmodel--andwhyitdoesn'tmatter
2NPandNPcompleteness
3Diagonalization
4Spacecomplexity
5Thepolynomialhierarchyandalternations
6Booleancircuits
7Randomizedcomputation
8Interactiveproofs
9Cryptography
10Quantumcomputation
11PCPtheoremandhardnessofapproximation:Anintroduction

PARTTWO:LOWERBOUNDSFORCONCRETECOMPUTATIONALMODELS
12Decisiontrees
13Communicationcomplexity
14Circuitlowerbounds:Complexitytheory'sWaterloo
15Proofcomplexity
16Algebraiccomputationmodels

PARTTHREE:ADVANCEDTOPICS
17Complexityofcounting
18Averagecasecomplexity:Levin'stheory
19Hardnessamplificationanderror-correctingcodes
20Derandomization
21Pseudorandomconstructions:Expandersandextractors
22ProofsofPCPtheoremsandtheFouriertransformtechnique
23Whyarecircuitlowerboundssodifficult?
Appendix:Mathematicalbackground
Hintsandselectedexercises
Maintheoremsanddefinitions
Bibliography
Index
Complexityclassindex