国外数学名著系列25：代数复杂性理论

图书标准信息

• 作者 [瑞士]比尔吉斯尔（Burgisser P.） 著
• 出版社 科学出版社
• 出版时间 2007-01
• 版次 1
• ISBN 9787030182999
• 定价 98.00元
• 装帧 精装
• 开本 其他
• 纸张 胶版纸
• 页数 618页
• 字数 760千字

【内容简介】

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

【目录】

Chapter1.Introduction
1.1Exercises
1.2OpenProblems
1.3Notes
PartⅠ.FundamentalAlgorithms
Chapter2.EfficientPolynomialArithmetic
2.1MultiplicationofPolynomialsI
2.2*MultiplicationofPolynomialsII
2.3*MultiplicationofSeveralPolynomials
2.4MultiplicationandInversionofPowerSeries
2.5*CompositionofPowerSeries
2.6Exercises
2.7OpenProblems
2.8Notes
Chapter3.EfficientAlgorithmswithBranching
3.1PolynomialGreatestCommonDivisors
3.2*LocalAnalysisoftheKnuth-SchonhageAlgorithm
3.3EvaluationandInterpolation
3.4*FastPointLocationinArrangementsofHyperplanes
3.5*Vapnik-ChervonenkisDimensionandEpsilon-Nets
3.6Exercises
3.7OpenProblems
3.8Notes
PartⅡ.ElementaryLowerBounds
Chapter4.ModelsofComputation
4.1Straight-LineProgramsandComplexity
4.2ComputationSequences
4.3*Autarky
4.4*ComputationTrees
4.5*ComputationTreesandStraight-linePrograms
4.6Exercises
4.7Notes
Chapter5.PreconditioningandTranscendenceDegree
5.1Preconditioning
5.2TranscendenceDegree
5.3*ExtensiontoLinearlyDisjointFields
5.4Exercises
5.5OpenProblems
5.6Notes
Chapter6.TheSubstitutionMethod
6.1DiscussionofIdeas
6.2LowerBoundsbytheDegreeofLinearization
6.3*ContinuedFractions,Quotients,andComposition
6.4Exercises
6.5OpenProblems
6.6Notes
Chapter7.DifferentialMethods
7.1ComplexityofTruncatedTaylorSeries
7.2ComplexityofPartialDerivatives
7.3Exercises
7.4OpenProblems
7.5Notes
PartⅢ.HighDegree
Chapter8.TheDegreeBound
8.1AFieldTheoreticVersionoftheDegreeBound
8.2GeometricDegreeandaBezoutInequality
8.3TheDegreeBound
8.4Applications
8.5*EstimatesfortheDegree
8.6*TheCaseofaFiniteField
8.7Exercises
8.8OpenProblems
8.9Notes
Chapter9.SpecificPolynomialswhichAreHardtoCompute
9.1AGeneticComputation
9.2PolynomialswithAlgebraicCoefficients
9.3Applications
9.4*PolynomialswithRapidlyGrowingIntegerCoefficients
9.5*ExtensiontootherComplexityMeasures
9.6Exercises
9.7OpenProblems
9.8Notes
Chapter10.BranchingandDegree
10.1ComputationTreesandtheDegreeBound
10.2ComplexityoftheEuclideanRepresentation
10.3*DegreePatternoftheEuclideanRepresentation
10.4Exercises
10.5OpenProblems
10.6Notes
Chapter11.BranchingandConnectivity
11.1EstimationoftheNumberofConnectedComponent
11.2LowerBoundsbytheNumberofConnectedComponents
11.3KnapsackandApplicationstoComputationalGeometry
11.4Exercises
11.5OpenProblems
11.6Notes
Chapter12.AdditiveComplexity
12.1Introduction
12.2*RealRootsofSparseSystemsofEquations
12.3ABoundontheAdditiveComplexity
12.4Exercises
12.5OpenProblems
12.6Notes
PartⅣ.LowDegree
Chapter13.LinearComplexity
13.1TheLinearComputationalModel
13.2FirstUpperandLowerBounds
13.3*AGraphTheoreticalApproach
13.4*LowerBoundsviaGraphTheoreticalMethods
13.5*GeneralizedFourierTransforms
13.6Exercises
13.7OpenProblems
13.8Notes
Chapter14.MultiplicativeandBilinearComplexity
14.1MultiplicativeComplexityofQuadraticMaps
14.2TheTensorialNotation
14.3RestrictionandConciseness
14.4OtherCharacterizationsofRank
14.5RankofthePolynomialMultiplication
14.6TheSemiringT
14.7Exercises
14.8OpenProblems
14.9Notes
Chapter15.AsymptoticComplexityofMatrixMultiplication
Chapter16.ProblemsRelatedtoMatrixMultiplication
Chapter17.LowerBoundsfortheComplexityofAlgebras
Chapter18.RankoverFiniteFieldsandCodes
Chapter19.Rankof2-Sliceand3-SliceTensors
Chapter20.TypicalTensorialRank
PartⅤ.CompleteProblems
Chapter21.PVersusNP：ANonuniformAlgebraicAnalogue
Bibliography
ListofNotation
Index