计算复杂性 影印版2025|PDF|Epub|mobi|kindle电子书版本百度云盘下载

计算复杂性 影印版PDF格式电子书版下载

注意：本站所有压缩包均有解压码： 点击下载压缩包解压工具

PART Ⅰ:ALG？RITHMS1

1 Problems and Algorithms3

1.1 Graph reachability3

1.2 Maximum flow and matching8

1.3 The traveling salesman problem13

1.4 Notes,references,and problems14

2 Turing machines19

2.1 Turing machine basics19

2.2 Turing machines as algorithms24

2.3 Turing machines with multiple strings26

2.4 Linear speedup32

2.5 Space bounds34

2.6 Random access machines36

2.7 Nondeterministic machines45

2.8 Notes,references,and problems51

3 Undecidability57

3.1 Universal Turing machines57

3.2 The halting problem58

3.3 More undecidability60

3.4 Notes,references,and problems66

PART Ⅱ:LOGIC71

4 Boolean logic73

4.1 Boolean Expressions76

4.2 Satisfiability and validity76

4.3 Boolean functions and circuits79

4.4 Notes,references,and problems84

5 First-order logic87

5.1 The syntax of first-order logic87

5.2 Models90

5.3 Valid expressions95

5.4 Axioms and proofs100

5.5 The completeness theorem105

5.6 Consequences of the completeness theorem110

5.7 Second-order logic113

5.8 Notes,references,and problems118

6 Undecidability in logic123

6.1 Axioms for number theory123

6.2 Computation as a number-theoretic concept127

6.3 Undecidability and incompleteness131

6.4 Notes,references,and problems135

PART Ⅲ:P AND NP137

7 Relations between complexity classes139

7.1 Complexity classes139

7.2 The hierarchy theorem143

7.3 The reachability method146

7.4 Notes,references,and problems154

8 Reductions and completeness159

8.1 Reductions159

8.2 Completeness165

8.3 Logical characterizations172

8.4 Notes,references,and problems177

9 NP-complete problems181

9.1 Problems in NP181

9.2 Variants of satisfiability183

9.3 Graph-theoretic problems188

9.4 Sets and numbers199

9.5 Notes,references,and problems207

10 coNP and function problems219

10.1 NP and coNP219

10.2 Primality222

10.3 Function problems227

10.4 Notes,references,and problems235

11 Randomized computation241

11.1 Randomized algorithms241

11.2 Randomized complexity classes253

11.3 Random sources259

11.4 Circuit complexity267

11.5 Notes,references,and problems272

12 Cryptography279

12.1 One-way functions279

12.2 Protocols287

12.3 Notes,references,and problems294

13 Approximability299

13.1 Approximation algorithms299

13.2 Approximation and complexity309

13.3 Nonapproximability319

13.4 Notes,references,and problems323

14 On P vs.NP329

14.1 The map of NP329

14.2 Isomorphism and density332

14.3 Oracles339

14.4 Monot.one circuits343

14.5 Notes,references,and problems350

PART Ⅳ:INSIDE P357

15 Parallel computation359

15.1 Parallel algorithms359

15.2 Parallel models of computation369

15.3 The class NC375

15.4 RNC algorithms381

15.5 Notes,references,and problems385

16 Logarithmic space395

16.1 The L？NL problem395

16.2 Alternation399

16.3 Undirected reachability401

16.4 Notes,references,and problems405

PART Ⅴ:BEYOND NP409

17 The polynomial hierarchy411

17.1 Optimization problems411

17.2 The hierarchy424

17.3 Notes,references,and problems433

18 Computation that counts439

18.1 The permanent439

18.2 The class ⊕P447

18.3 Notes,references,and problems452

19 Polynomial space455

19.1 Alternation and games455

19.2 Games against nature and interactive protocols469

19.3 More PSPACE-complete problems480

19.4 Notes,references,and problems487

20 A glimpse beyond491

20.1 Exponential time491

20.2 Notes,references,and problems499

Index509

Author index519