计算复杂性

图书标准信息

• 作者 帕帕李米特里乌 著
• 出版社 清华大学出版社
• 出版时间 2004-09
• 版次 1
• ISBN 9787302089551
• 定价 59.00元
• 装帧 平装
• 开本 其他
• 纸张 胶版纸
• 页数 523页

【内容简介】

　　计算复杂性理论的研究是计算机科学最重要的研究领域之一，而ChristosH．Papadmitriou是该领域最著名的专家之一。本书是一本全面阐述计算复杂性理论及其近年来进展的教科书，主要包含算法图灵机、可计算性等有关计算复杂性理论的基本概念；布尔逻辑、一阶逻辑、逻辑中的不可判定性等复杂性理论的基础知识；P与NP、NP完全等各复杂性类的概念及其之间的关系等复杂性理论的核心内容；随机算法、近似算法、并行算法及其复杂性理论；以及NP之外如多项式空间等复杂性类的介绍。
　　本书内容丰富，体系严谨，证明简洁，叙述深入浅出，并配有大量的练习和文献引用。本书不但适合作为研究生或本科高年级学生的教材，也适合从事算法和计算机复杂性研究的人员参考。

【目录】

PARTI：ALGORITHMS
1ProblemsandAlgorithms
1.1Graphreachability
1.2Maximumflowandmatching
1.3Thetravelingsalesmanproblem
1.4Notes，references，andproblems
2Turingmachines
2.1Turingmachinebasics
2.2Turingmachinesasalgorithms
2.3Turingmachineswithmultiplestrings
2.4Linearspeedup
2.5Spacebounds
2.6Randomaccessmachines
2.7Nondeterministicmachines
2.8Notes，references，andproblems
3Undecidability
3.1UniversalTuringmachines
3.2Thehaltingproblem
3.3Moreundecidability
3.4Notes，references，andproblems
PARTII：LOGIC
4Booleanlogic
4.1BooleanExpressions
4.2Satisfiabilityandvalidity
4.3Booleanfunctionsandcircuits
4.4Notes，references，andproblems
5First-orderlogic
5.1Thesyntaxoffirst-orderlogic
5.2Models
5.3Validexpressions
5.4Axiomsandproofs
5.5Thecompletenesstheorem
5.6Consequencesofthecompletenesstheorem
5.7Second-orderlogic
5.8Notes，references，andproblems
6Undecidabilityinlogic
6.1Axiomsfornumbertheory
6.2Computationasanumber-theoreticconcept
6.3Undecidabilityandincompleteness
6.4Notes，references，andproblems
PARTIII：PANDNP
7Relationsbetweencomplexityclasses
7.1Complexityclasses
7.2Thehierarchytheorem
7.3Thereachabilitymethod
7.4Notes，references，andproblems
8Reductionsandcompleteness
8.1Reductions
8.2Completeness
8.3Logicalcharacterizations
8.4Notes，referencess，andproblems
9NP-completeproblems
9.1ProblemsinNP
9.2Variantsofsatisfiability
9.3Graph-theoreticproblems
9.4Setsandnumbers
9.5Notes，references，andproblems
10coNPandfunctionproblems
10.1NPandcoNP
10.2Primality
10.3Functionproblems
10.4Notes，references，andproblems
11Randomizedcomputation
11.1Randomizedalgorithms
11.2Randomizedcomplexityclasses
11.3Randomsources
11.4Circuitcomplexity
11.5Notes，references，andproblems
12Cryptography
12.1One-wayfunctions
12.2Protocols
12.3Notes，references，andproblems
13Approximability
13.1Approximationalgorithms
13.2Approximationandcomplexity
13.3Nonapproximability
13.4Notes，references，andproblems
14OnPvs.NP
14.1ThemapofNP
14.2Isomorphismanddensity
14.3Oracles
14.4Monotonecircuits
14.5Notes，references，andproblems
PARTIV：INSIDEP
15Parallelcomputation
15.1Parallelalgorithms
15.2Parallelmodelsofcomputation
15.3TheclassNC
15.4RNCalgorithms
15.5Notes，references，andproblems
16Logarithmicspace
16.1TheL=NLproblem
16.2Alternation
16.3Undirectedreachability
16.4Notes，references，andproblems
PARTV：BEYONDNP
17Thepolynomialhierarchy
17.1Optimizationproblems
17.2Thehierarchy
17.3Notes，references，andproblems
18Computationthatcounts
18.1Thepermanent
18.2TheClassP
18.3Notes，references，andproblems
19Polynomialspace
19.1Alternationandgames
19.2Gamesagainstnatureandinteractiveprotocols
19.3MorePSPACE-completeproblems
19.4Notes，references，andproblems
20Aglimpsebeyond
20.1Exponentialtime
20.2Notes，references，andproblems
Index
Authorindex