计算复杂性的现代方法

2012-03

ISBN: 9787510042867

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

17Complexityofcounting
18Averagecasecomplexity:Levin'stheory
19Hardnessamplificationanderror-correctingcodes
20Derandomization
21Pseudorandomconstructions:Expandersandextractors
22ProofsofPCPtheoremsandtheFouriertransformtechnique
23Whyarecircuitlowerboundssodifficult?
Appendix:Mathematicalbackground
Hintsandselectedexercises
Maintheoremsanddefinitions
Bibliography
Index
Complexityclassindex
• 内容简介:
《计算复杂性的现代方法》是一部将所有有关复杂度知识理论集于一体的教程。将最新进展和经典结果结合起来，是一部很难得的研究生入门级教程。既是相关科研人员的一部很好的参考书，也是自学人员很难得的一本很好自学教程。本书一开始引入该领域的最基本知识，然后逐步深入，介绍更多深层次的结果，每章末都附有练习。对复杂度感兴趣的人士，物理学家，数学家以及科研人员这本书都是相当受益。
• 目录:
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

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

• 九品
河北省衡水市
150.00

[波兰]雅·伊瓦什凯维奇；易丽君 裴远颖

[俄]波利亚科夫 著

[爱尔兰]罗迪·道伊尔 著；郭国良 彭真丹 译

[俄]德米特里·利哈乔夫 著；焦东建、董茉莉 译

[英]西蒙·沙玛

[美]伊莎贝尔·威尔克森 著；姚向辉 顾冰珂 译

[美]斯蒂芬·格林布拉特（(Stephen Greenblatt)） 作者；罗颖男 译