代数复杂性理论PDF|Epub|txt|kindle电子书版本网盘下载

代数复杂性理论PDF格式电子书版下载

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

Chapter 1. Introduction1

1.1 Exercises20

1.2 Open Problems23

1.3 Notes23

Part Ⅰ. Fundamental Algorithms27

Chapter 2. Efficient Polynomial Arithmetic27

2.1 Multiplication of Polynomials Ⅰ28

2.2 Multiplication of Polynomials Ⅱ34

2.3 Multiplication of Several Polynomials38

2.4 Multiplication and Inversion of Power Series44

2.5 Composition of Power Series47

2.6 Exercises53

2.7 Open Problems57

2.8 Notes58

Chapter 3. Efficient Algorithms with Branching61

3.1 Polynomial Greatest Common Divisors61

3.2 Local Analysis of the Knuth-Schonhage Algorithm71

3.3 Evaluation and Interpolation75

3.4 Fast Point Location in Arrangements of Hyperplanes79

3.5 Vapnik-Chervonenkis Dimension and Epsilon-Nets84

3.6 Exercises90

3.7 Open Problems97

3.8 Notes98

Part Ⅱ. Elementary Lower Bounds103

Chapter 4. Models of Computation103

4.1 Straight-Line Programs and Complexity103

4.2 Computation Sequences109

4.3 Autarky111

4.4 Computation Trees113

4.5 Computation Trees and Straight-line Programs118

4.6 Exercises121

4.7 Notes124

Chapter 5. Preconditioning and Transcendence Degree125

5.1 Preconditioning125

5.2 Transcendence Degree130

5.3 Extension to Linearly Disjoint Fields134

5.4 Exercises136

5.5 Open Problems142

5.6 Notes142

Chapter 6. The Substitution Method143

6.1 Discussion of Ideas144

6.2 Lower Bounds by the Degree of Linearization148

6.3 Continued Fractions，Quotients，and Composition151

6.4 Exercises157

6.5 Open Problems159

6.6 Notes159

Chapter 7. Differential Methods161

7.1 Complexity of Truncated Taylor Series161

7.2 Complexity of Partial Derivatives164

7.3 Exercises167

7.4 Open Problems168

7.5 Notes168

Part Ⅲ. High Degree171

Chapter 8. The Degree Bound171

8.1 A Field Theoretic Version of the Degree Bound171

8.2 Geometric Degree and a Bezout Inequality178

8.3 The Degree Bound182

8.4 Applications186

8.5 Estimates for the Degree192

8.6 The Case of a Finite Field195

8.7 Exercises198

8.8 Open Problems205

8.9 Notes205

Chapter 9.Specific Polynomials which Are Hard to Compute207

9.1 A Generic Computation207

9.2 Polynomials with Algebraic Coefficients211

9.3 Applications218

9.4 Polynomials with Rapidly Growing Integer Coefficients224

9.5 Extension to other Complexity Measures230

9.6 Exercises236

9.7 Open Problems243

9.8 Notes243

Chapter 10. Branching and Degree245

10.1 Computation Trees and the Degree Bound245

10.2 Complexity of the Euclidean Representation248

10.3 Degree Pattern of the Euclidean Representation253

10.4 Exercises260

10.5 Open Problems263

10.6 Notes264

Chapter 11. Branching and Connectivity265

11.1 Estimation of the Number of Connected Components265

11.2 Lower Bounds by the Number of Connected Components272

11.3 Knapsack and Applications to Computational Geometry275

11.4 Exercises278

11.5 Open Problems282

11.6 Notes283

Chapter 12. Additive Complexity287

12.1 Introduction287

12.2 Real Roots of Sparse Systems of Equations289

12.3 A Bound on the Additive Complexity296

12.4 Exercises298

12.5 Open Problems300

12.6 Notes301

Part Ⅳ. Low Degree305

Chapter 13. Linear Complexity305

13.1 The Linear Computational Model305

13.2 First Upper and Lower Bounds309

13.3 A Graph Theoretical Approach314

13.4 Lower Bounds via Graph Theoretical Methods318

13.5 Generalized Fourier Transforms326

13.6 Exercises345

13.7 Open Problems348

13.8 Notes348

Chapter 14. Multiplicative and Bilinear Complexity351

14.1 Multiplicative Complexity of Quadratic Maps351

14.2 The Tensorial Notation357

14.3 Restriction and Conciseness361

14.4 Other Characterizations of Rank365

14.5 Rank of the Polynomial Multiplication367

14.6 The Semiring T368

14.7 Exercises370

14.8 Open Problems373

14.9 Notes373

Chapter 15. Asymptotic Complexity of Matrix Multiplication375

15.1 The Exponent of Matrix Multiplication375

15.2 First Estimates of the Exponent377

15.3 Scalar Restriction and Extension381

15.4 Degeneration and Border Rank384

15.5 The Asymptotic Sum Inequality389

15.6 First Steps Towards the Laser Method391

15.7 Tight Sets396

15.8 The Laser Method401

15.9 Partial Matrix Multiplication407

15.10 Rapid Multiplication of Rectangular Matrices411

15.11 Exercises412

15.12 Open Problems419

15.13 Notes420

Chapter 16. Problems Related to Matrix Multiplication425

16.1 Exponent of Problems425

16.2 Triangular Inversion427

16.3 L UP-decomposition428

16.4 Matrix Inversion and Determinant430

16.5 Transformation to Echelon Form431

16.6 The Characteristic Polynomial435

16.7 Computing a Basis for the Kernel439

16.8 Orthogonal Basis Transform441

16.9 Matrix Multiplication and Graph Theory445

16.10 Exercises447

16.11 Open Problems451

16.12 Notes452

Chapter 17. Lower Bounds for the Complexity of Algebras455

17.1 First Steps Towards Lower Bounds455

17.2 Multiplicative Complexity of Associative Algebras463

17.3 Multiplicative Complexity of Division Algebras470

17.4 Commutative Algebras of Minimal Rank474

17.5 Exercises481

17.6 Open Problems484

17.7 Notes485

Chapter 18. Rank over Finite Fields and Codes489

18.1 Linear Block Codes489

18.2 Linear Codes and Rank491

18.3 Polynomial Multiplication over Finite Fields492

18.4 Matrix Multiplication over Finite Fields494

18.5 Rank of Finite Fields496

18.6 Exercises498

18.7 Open Problems502

18.8 Notes502

Chapter 19. Rank of 2-Slice and 3-Slice Tensors505

19.1 The WeierstraB-Kronecker Theory505

19.2 Rank of 2-Slice Tensors508

19.3 Rank of 3-Slice Tensors512

19.4 Exercises516

19.5 Notes519

Chapter 20. Typical Tensorial Rank521

20.1 Geometric Description521

20.2 Upper Bounds on the Typical Rank524

20.3 Dimension of Configurations in Formats531

20.4 Exercises534

20.5 Open Problems536

20.6 Appendix：Topological Degeneration536

20.7 Notes539

Part Ⅴ. Complete Problems543

Chapter 21. P Versus NP：A Nonuniform Algebraic Analogue543

21.1 Cook’s Versus Valiant’s Hypothesis543

21.2 p-Definability and Expression Size550

21.3 Universality of the Determinant554

21.4 Completeness of the Permanent556

21.5 The Extended Valiant Hypothesis561

21.6 Exercises569

21.7 Open Problems574

21.8 Notes574

Bibliography577

List of Notation601

Index609