代数复杂性理论

Chapter 1.Introduction

1.1 Exercises

1.2 Open Problems

1.3 Notes

PartⅠ.Fundamental Algorithms

Chapter 2. Efficient Polynomial Arithmetic

2.1 Multiplication of Polynomials I

2.2* Multiplication of Polynomials II

2.3* Multiplication of Several Polynomials

2.4 Multiplication and Inversion of Power Series

2.5* Composition of Power Series

2.6 Exercises

2.7 Open Problems

2.8 Notes

Chapter 3. Efficient Algorithms with Branching

3.1 Polynomial Greatest Common Divisors

3.2* Local Analysis of the Knuth-Schonhage Algorithm

3.3 Evaluation and Interpolation

3.4* Fast Point Location in Arrangements of Hyperplanes

3.5* Vapnik-Chervonenkis Dimension and Epsilon-Nets

3.6 Exercises

3.7 Open Problems

3.8 Notes

PartⅡ.Elementary Lower Bounds

Chapter 4. Models of Computation

4.1 Straight-Line Programs and Complexity

4.2 Computation Sequences

4.3* Autarky

4.4* Computation Trees

4.5* Computation Trees and Straight-line Programs

4.6 Exercises

4.7 Notes

Chapter 5. Preconditioning and Transcendence Degree

5.1 Preconditioning

5.2 Transcendence Degree

5.3* Extension to Linearly Disjoint Fields

5.4 Exercises

5.5 Open Problems

5.6 Notes

Chapter 6. The Substitution Method

6.1 Discussion of Ideas

6.2 Lower Bounds by the Degree of Linearization

6.3* Continued Fractions, Quotients, and Composition

6.4 Exercises

6.5 Open Problems

6.6 Notes

Chapter 7. Differential Methods

7.1 Complexity of Truncated Taylor Series

7.2 Complexity of Partial Derivatives

7.3 Exercises

7.4 Open Problems

7.5 Notes

Part Ⅲ.High Degree

Chapter 8. The Degree Bound

8.1 A Field Theoretic Version of the Degree Bound

8.2 Geometric Degree and a Bezout Inequality

8.3 The Degree Bound

8.4 Applications

8.5* Estimates for the Degree

8.6* The Case of a Finite Field

8.7 Exercises

8.8 Open Problems

8.9 Notes

Chapter 9. Specific Polynomials which Are Hard to Compute

9.1 A Genetic Computation

9.2 Polynomials with Algebraic Coefficients

9.3 Applications

9.4* Polynomials with Rapidly Growing Integer Coefficients

9.5* Extension to other Complexity Measures

9.6 Exercises

9.7 Open Problems

9.8 Notes

Chapter 10. Branching and Degree

10.1 Computation Trees and the Degree Bound

10.2 Complexity of the Euclidean Representation

10.3* Degree Pattern of the Euclidean Representation

10.4 Exercises

10.5 Open Problems

10.6 Notes

Chapter 11. Branching and Connectivity

11.1 Estimation of the Number of Connected Component

11.2 Lower Bounds by the Number of Connected Components

11.3 Knapsack and Applications to Computational Geometry

11.4 Exercises

11.5 Open Problems

11.6 Notes

Chapter 12. Additive Complexity

12.1 Introduction

12.2* Real Roots of Sparse Systems of Equations

12.3 A Bound on the Additive Complexity

12.4 Exercises

12.5 Open Problems

12.6 Notes

Part Ⅳ.Low Degree

Chapter 13. Linear Complexity

13.1 The Linear Computational Model

13.2 First Upper and Lower Bounds

13.3* A Graph Theoretical Approach

13.4* Lower Bounds via Graph Theoretical Methods

13.5* Generalized Fourier Transforms

13.6 Exercises

13.7 Open Problems

13.8 Notes

Chapter 14. Multiplicative and Bilinear Complexity

14.1 Multiplicative Complexity of Quadratic Maps

14.2 The Tensorial Notation

14.3 Restriction and Conciseness

14.4 Other Characterizations of Rank

14.5 Rank of the Polynomial Multiplication

14.6 The Semiring T

14.7 Exercises

14.8 Open Problems

14.9 Notes

Chapter 15. Asymptotic Complexity of Matrix Multiplication

Chapter 16. Problems Related to Matrix Multiplication

Chapter 17. Lower Bounds for the Complexity of Algebras

Chapter 18. Rank over Finite Fields and Codes

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

Chapter 20. Typical Tensorial Rank

Part Ⅴ.Complete Problems

Chapter 21. P Versus NP：A Nonuniform Algebraic Analogue

Bibliography

List of Notation

Index

从出版方面来讲，除了较好较快地出版我们自己的成果外，引进国外的先进出版物无疑也是十分重要与必不可少的。从数学来说，施普林格（Springer）出版社至今仍然是世界上最具权威的出版社。科学出版社影印一批他们出版的好的新书，使我国广大数学家能以较低的价格购买，特别是在边远地区工作的数学家能普遍见到这些书，无疑是对推动我国数学的科研与教学十分有益的事。
　　这次科学出版社购买了版权，一次影印了23本施普林格出版社出版的数学书，就是一件好事，也是值得继续做下去的事情。大体上分一下，这28本书中，包括基础数学书5本，应用数学书6本与计算数学书12本，其中有些书也具有交叉性质。这些书都是很新的，2000年以后出版的占绝大部分，共计16本，其余的也是1990年以后出版的。这些书可以使读者较快地了解数学某方面的前沿，例如基础数学中的数论、代数与拓扑三本，都是由该领域大数学家编著的“数学百科全书”的分册。对从事这方面研究的数学家了解该领域的前沿与全貌很有帮助。按照学科的特点，基础数学类的书以“经典”为主，应用和计算数学类的书“前沿”为主。这些书的作者多数是国际知名的大数学家，例如《拓扑学》一书的作者诺维科夫是俄罗斯科学院的院士，曾获“菲尔兹奖”和“沃尔夫数学奖”。这些大数学家的著作无疑将会对我国的科研人员起到非常好的指导作用。
　　当然，23本书只能涵盖数学的一部分，所以，这项工作还应该继续做下去。更进一步，有些读者面较广的好书还应该翻译成中文出版，使之有更大的读者群。