计算复杂性

图书标准信息

• 作者 [以色列]戈德赖希 著
• 出版社 人民邮电出版社
• 出版时间 2010-04
• 版次 1
• ISBN 9787115224002
• 定价 99.00元
• 装帧 平装
• 开本 16开
• 纸张 胶版纸
• 页数 603页
• 字数 754千字
• 正文语种 英语
• 原版书名 Computational Complexity: A Conceptual Perspective
• 丛书 图灵原版计算机科学系列

【内容简介】

　　复杂性理论是计算机科学的理论基础的核心。本书是著名计算机科学家OdedGoldreich的力作，书中对计算任务固有复杂性研究进行了概念性介绍，全面分析了复杂性理论的现代主题。
　　本书涉及复杂性理论的很多子领域（如难度放大、伪随机性及概率证明系统等），涵盖了NP完整性、空间复杂性、随机性和计数、伪随机数生成器等内容，还在附录里面介绍了现代密码学基础等。
　　本书内容严谨，可读性强，适合作为高年级本科生、研究生的教材。同时，书中展示了复杂性理论的很多子领域，也适合领域专家参考。

【作者简介】

　　OdedGoldreich，以色列魏茨曼科学研究院（WeizmannInstituteofScience）计算机科学教授，MeyerW.Weisgal讲席教授。他是SIAMJournalonComputing、JournalofCryptology和ComputationalComplexity杂志的特约编辑。其主要研究方向是计算复杂性、随机性与计算以及密码学，他在这几个方面均有享誉世界的研究成果。作为一名活跃的学者，他发表了大量的论文，还著有两卷本的FoundationsofCryptography（《密码学基础》）和ModernCryptography，ProbabilisticProofsandPseudorandomness等专著。

【目录】

1IntroductionandPreliminaries1
1.1Introduction1
1.1.1ABriefOverviewofComplexityTheory2
1.1.2CharacteristicsofComplexityTheory6
1.1.3ContentsofThisBook8
1.1.4ApproachandStyleofThisBook12
1.1.5StandardNotationsandOtherConventions16
1.2ComputationalTasksandModels17
1.2.1Representation18
1.2.2ComputationalTasks18
1.2.3UniformModels(Algorithms)20
1.2.4Non-uniformModels(CircuitsandAdvice)36
1.2.5ComplexityClasses42
ChapterNotes43

2P，NP，andNP-Completeness44
2.1ThePVersusNPQuestion46
2.1.1TheSearchVersion：FindingVersusChecking47
2.1.2TheDecisionVersion：ProvingVersusVerifying50
2.1.3EquivalenceoftheTwoFormulations54
2.1.4TwoTechnicalCommentsRegardingNP55
2.1.5TheTraditionalDefinitionofNP55
2.1.6InSupportofPDifferentfromNP57
2.1.7PhilosophicalMeditations58
2.2Polynomial-TimeReductions58
2.2.1TheGeneralNotionofaReduction59
2.2.2ReducingOptimizationProblemstoSearchProblems61
2.2.3Self-ReducibilityofSearchProblems63
2.2.4DigestandGeneralPerspective67
2.3NP-Completeness67
2.3.1Definitions68
2.3.2TheExistenceofNP-CompleteProblems69
2.3.3SomeNaturalNP-CompleteProblems71
2.3.4NPSetsThatAreNeitherinPnorNP-Complete81
2.3.5ReflectionsonCompleteProblems85
2.4ThreeRelativelyAdvancedTopics87
2.4.1PromiseProblems87
2.4.2OptimalSearchAlgorithmsforNP92
2.4.3TheClasscoNPandItsIntersectionwithNP94
ChapterNotes97
Exercises99

3VariationsonPandNP108
3.1Non-uniformPolynomialTime(P/poly)108
3.1.1BooleanCircuits109
3.1.2MachinesThatTakeAdvice111
3.2ThePolynomial-TimeHierarchy(PH)113
3.2.1AlternationofQuantifiers114
3.2.2Non-deterministicOracleMachines117
3.2.3TheP/polyVersusNPQuestionandPH119
ChapterNotes121
Exercises122

4MoreResources，MorePower127
4.1Non-uniformComplexityHierarchies128
4.2TimeHierarchiesandGaps129
4.2.1TimeHierarchies129
4.2.2TimeGapsandSpeedup136
4.3SpaceHierarchiesandGaps139
ChapterNotes139
Exercises140

5SpaceComplexity143
5.1GeneralPreliminariesandIssues144
5.1.1ImportantConventions144
5.1.2OntheMinimalAmountofUsefulComputationSpace145
5.1.3TimeVersusSpace146
5.1.4CircuitEvaluation153
5.2LogarithmicSpace153
5.2.1TheClassL154
5.2.2Log-SpaceReductions154
5.2.3Log-SpaceUniformityandStrongerNotions155
5.2.4UndirectedConnectivity155
5.3Non-deterministicSpaceComplexity162
5.3.1TwoModels162
5.3.2NLandDirectedConnectivity164
5.3.3ARetrospectiveDiscussion171
5.4PSPACEandGames172
ChapterNotes175
Exercises175

6RandomnessandCounting184
6.1ProbabilisticPolynomialTime185
6.1.1BasicModelingIssues186
6.1.2Two-SidedError：TheComplexityClassBPP189
6.1.3One-SidedError：TheComplexityClassesRPandcoRP193
6.1.4Zero-SidedError：TheComplexityClassZPP199
6.1.5RandomizedLog-Space199
6.2Counting202
6.2.1ExactCounting202
6.2.2ApproximateCounting211
6.2.3SearchingforUniqueSolutions217
6.2.4UniformGenerationofSolutions220
ChapterNotes227
Exercises230

7TheBrightSideofHardness241
7.1One-WayFunctions242
7.1.1GeneratingHardInstancesandOne-WayFunctions243
7.1.2AmplificationofWeakOne-WayFunctions245
7.1.3Hard-CorePredicates250
7.1.4ReflectionsonHardnessAmplification255
7.2HardProblemsinE255
7.2.1AmplificationwithRespecttoPolynomial-SizeCircuits257
7.2.2AmplificationwithRespecttoExponential-SizeCircuits270
ChapterNotes277
Exercises278

8PseudorandomGenerators284
Introduction285
8.1TheGeneralParadigm288
8.2General-PurposePseudorandomGenerators290
8.2.1TheBasicDefinition291
8.2.2TheArchetypicalApplication292
8.2.3ComputationalIndistinguishability295
8.2.4AmplifyingtheStretchFunction299
8.2.5Constructions301
8.2.6Non-uniformlyStrongPseudorandomGenerators304
8.2.7StrongerNotionsandConceptualReflections305
8.3DerandomizationofTime-ComplexityClasses307
8.3.1DefiningCanonicalDerandomizers308
8.3.2ConstructingCanonicalDerandomizers310
8.3.3TechnicalVariationsandConceptualReflections313
8.4Space-BoundedDistinguishers315
8.4.1DefinitionalIssues316
8.4.2TwoConstructions318
8.5Special-PurposeGenerators325
8.5.1PairwiseIndependenceGenerators326
8.5.2Small-BiasGenerators329
8.5.3RandomWalksonExpanders332
ChapterNotes334
Exercises337

9ProbabilisticProofSystems349
9.1InteractiveProofSystems352
9.1.1MotivationandPerspective352
9.1.2Definition354
9.1.3ThePowerofInteractiveProofs357
9.1.4VariantsandFinerStructure：AnOverview363
9.1.5OnComputationallyBoundedProvers：AnOverview366
9.2Zero-KnowledgeProofSystems368
9.2.1DefinitionalIssues369
9.2.2ThePowerofZero-Knowledge372
9.2.3ProofsofKnowledge-AParentheticalSubsection378
9.3ProbabilisticallyCheckableProofSystems380
9.3.1Definition381
9.3.2ThePowerofProbabilisticallyCheckableProofs383
9.3.3PCPandApproximation398
9.3.4MoreonPCPItself：AnOverview401
ChapterNotes404
Exercises406

10RelaxingtheRequirements416
10.1Approximation417
10.1.1SearchorOptimization418
10.1.2DecisionorPropertyTesting423
10.2Average-CaseComplexity428
10.2.1TheBasicTheory430
10.2.2Ramifications442
ChapterNotes451
Exercises453

Epilogue461
AppendixA：GlossaryofComplexityClasses463
A.1Preliminaries463
A.2Algorithm-BasedClasses464
A.2.1TimeComplexityClasses464
A.2.2SpaceComplexityClasses467
A.3Circuit-BasedClasses467

AppendixB：OntheQuestforLowerBounds469
B.1Preliminaries469
B.2BooleanCircuitComplexity471
B.2.1BasicResultsandQuestions472
B.2.2MonotoneCircuits473
B.2.3Bounded-DepthCircuits473
B.2.4FormulaSize474
B.3ArithmeticCircuits475
B.3.1UnivariatePolynomials476
B.3.2MultivariatePolynomials476
B.4ProofComplexity478
B.4.1LogicalProofSystems480
B.4.2AlgebraicProofSystems480
B.4.3GeometricProofSystems481

AppendixC：OntheFoundationsofModernCryptography482
C.1IntroductionandPreliminaries482
C.1.1TheUnderlyingPrinciples483
C.1.2TheComputationalModel485
C.1.3OrganizationandBeyond486
C.2ComputationalDifficulty487
C.2.1One-WayFunctions487
C.2.2Hard-CorePredicates489
C.3Pseudorandomness490
C.3.1ComputationalIndistinguishability490
C.3.2PseudorandomGenerators491
C.3.3PseudorandomFunctions492
C.4Zero-Knowledge494
C.4.1TheSimulationParadigm494
C.4.2TheActualDefinition494
C.4.3AGeneralResultandaGenericApplication495
C.4.4DefinitionalVariationsandRelatedNotions497
C.5EncryptionSchemes500
C.5.1Definitions502
C.5.2Constructions504
C.5.3BeyondEavesdroppingSecurity505
C.6SignaturesandMessageAuthentication507
C.6.1Definitions508
C.6.2Constructions509
C.7GeneralCryptographicProtocols511
C.7.1TheDefinitionalApproachandSomeModels512
C.7.2SomeKnownResults517
C.7.3ConstructionParadigmsandTwoSimpleProtocols517
C.7.4ConcludingRemarks522

AppendixD：ProbabilisticPreliminariesandAdvancedTopicsinRandomization523
D.1ProbabilisticPreliminaries523
D.1.1NotationalConventions523
D.1.2ThreeInequalities524
D.2Hashing528
D.2.1Definitions528
D.2.2Constructions529
D.2.3TheLeftoverHashLemma529
D.3Sampling533
D.3.1FormalSetting533
D.3.2KnownResults534
D.3.3Hitters535
D.4RandomnessExtractors536
D.4.1DefinitionsandVariousPerspectives537
D.4.2Constructions541
AppendixE：ExplicitConstructions545
E.1Error-CorrectingCodes546
E.1.1BasicNotions546
E.1.2AFewPopularCodes547
E.1.3TwoAdditionalComputationalProblems551
E.1.4AList-DecodingBound553
E.2ExpanderGraphs554
E.2.1DefinitionsandProperties555
E.2.2Constructions561
AppendixF：SomeOmittedProofs566
F.1ProvingThatPHReducesto#P566
F.2ProvingThatIP(f)?AM(O(f))?AM(f)572
F.2.1EmulatingGeneralInteractiveProofsbyAM-Games572
F.2.2LinearSpeedupforAM578
AppendixG：SomeComputationalProblems583
G.1Graphs583
G.2BooleanFormulae585
G.3FiniteFields，Polynomials，andVectorSpaces586
G.4TheDeterminantandthePermanent587
G.5PrimesandCompositeNumbers587
Bibliography589
Index601