未读消息消息

购物车

我的订单

个人中心

店铺

我的订单收藏

拍卖

拍卖交易我的竞拍收藏

我的好友资金账户

卖家中心

客服 |

帮助中心 9:00-20:30 在线留言

客服电话

010-89648155

服务时间

客服咨询 8:00-21:00

纠纷处理 9:00-21:00

图书审核 9:00-18:00

监督与建议

请选择

手机孔网

计算复杂性

作者: [以色列] 戈德赖希著

出版社: 人民邮电出版社

出版时间: 2010-04

版次: 1

ISBN: 9787115224002

定价: 99.00

装帧: 平装

开本: 16开

纸张: 胶版纸

页数: 603页

字数: 754千字

正文语种: 英语

原版书名: Computational Complexity: A Conceptual Perspective

丛书: 图灵原版计算机科学系列

分类: 计算机与互联网

1 张插图图片

13人买过

　　复杂性理论是计算机科学的理论基础的核心。本书是著名计算机科学家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
内容简介:
　　复杂性理论是计算机科学的理论基础的核心。本书是著名计算机科学家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

查看详情

计算复杂性

内容简介:

作者简介:

目录: