代數(shù)復(fù)雜性理論

內(nèi)容概要

從出版方面來講，除了較好較快地出版我們自己的成果外，引進(jìn)國外的先進(jìn)出版物無疑也是十分重要與必不可少的。從數(shù)學(xué)來說，施普林格（Springer）出版社至今仍然是世界上最具權(quán)威的出版社?？茖W(xué)出版社影印一批他們出版的好的新書，使我國廣大數(shù)學(xué)家能以較低的價格購買，特別是在邊遠(yuǎn)地區(qū)工作的數(shù)學(xué)家能普遍見到這些書，無疑是對推動我國數(shù)學(xué)的科研與教學(xué)十分有益的事。    這次科學(xué)出版社購買了版權(quán)，一次影印了23本施普林格出版社出版的數(shù)學(xué)書，就是一件好事，也是值得繼續(xù)做下去的事情。大體上分一下，這28本書中，包括基礎(chǔ)數(shù)學(xué)書5本，應(yīng)用數(shù)學(xué)書6本與計算數(shù)學(xué)書12本，其中有些書也具有交叉性質(zhì)。這些書都是很新的，2000年以后出版的占絕大部分，共計16本，其余的也是1990年以后出版的。這些書可以使讀者較快地了解數(shù)學(xué)某方面的前沿，例如基礎(chǔ)數(shù)學(xué)中的數(shù)論、代數(shù)與拓?fù)淙?，都是由該領(lǐng)域大數(shù)學(xué)家編著的“數(shù)學(xué)百科全書”的分冊。對從事這方面研究的數(shù)學(xué)家了解該領(lǐng)域的前沿與全貌很有幫助。按照學(xué)科的特點(diǎn)，基礎(chǔ)數(shù)學(xué)類的書以“經(jīng)典”為主，應(yīng)用和計算數(shù)學(xué)類的書“前沿”為主。這些書的作者多數(shù)是國際知名的大數(shù)學(xué)家，例如《拓?fù)鋵W(xué)》一書的作者諾維科夫是俄羅斯科學(xué)院的院士，曾獲“菲爾茲獎”和“沃爾夫數(shù)學(xué)獎”。這些大數(shù)學(xué)家的著作無疑將會對我國的科研人員起到非常好的指導(dǎo)作用。    當(dāng)然，23本書只能涵蓋數(shù)學(xué)的一部分，所以，這項(xiàng)工作還應(yīng)該繼續(xù)做下去。更進(jìn)一步，有些讀者面較廣的好書還應(yīng)該翻譯成中文出版，使之有更大的讀者群。

作者簡介

作者：(瑞士)Peter Burgisser (瑞士)Michael Clausen (瑞士)M.Amin Shokrollahi

書籍目錄

Chapter 1.Introduction　1.1 Exercises　1.2 Open Problems　1.3 NotesPartⅠ.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 NotesPartⅡ.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 NotesPart Ⅲ.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 NotesPart Ⅳ.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 RankPart Ⅴ.Complete Problems　Chapter 21. P Versus NP：A Nonuniform Algebraic AnalogueBibliographyList of NotationIndex

圖書封面

圖書標(biāo)簽Tags

無

評論、評分、閱讀與下載

---

    代數(shù)復(fù)雜性理論 PDF格式下載

---