代数复杂性理论（影印版）

定　价：¥98.00

作　者：	（瑞）比尔吉斯尔、等
出版社：	科学出版社
丛编项：	国外数学名著系列
标　签：	暂缺

购买这本书可以去

ISBN：	9787030182999	出版时间：	2007-01-01	包装：	精装
开本：	16开	页数：	618	字数：

内容简介

　　In this book we focus on Algebraic Complexity Theory， the study of the intrinsic algorithmic difficulty of algebraic problems within an algebraic model of computation. Motivated by questions of numerical and symbolic computation， this branch of research originated in 1954 when Ostrowski [403] inquired about the optimality of Homer's rule. Algebraic complexity theory grew rapidly and has since become a well-established area of research. However， with the exception of the now classic monograph by Borodin and Munro， published in 1975， a systematic treatment of this theory is not available. .This book is intended to be a comprehensive text which presents both traditional material and recent research in algebraic complexity theory in a coherent way. Requiring only some basic algebra and offering over 350 exercises， it should be well-suited as a textbook for beginners at the graduate level. With its extensive bibliographic notes covering nearly 600 research papers， it might also serve as a reference book. ...

作者简介

暂缺《代数复杂性理论（影印版）》作者简介

图书目录

Chapter1.Introduction
1.1Exercises.
1.2OpenProblems
1.3Notes
PartI.FundamentalAlgorithms
Chapter2.EfficientPolynomialArithmetic
2.1MultiplicationofPolynomialsI
2.2*MultiplicationofPolynomialsII
2.3*MultiplicationofSeveralPolynomials
2.4MultiplicationandInversionofPowerSeries
2.5*CompositionofPowerSeries
2.6Exercises
2.7OpenProblems
2.8Notes
Chapter3.EfficientAlgorithmswithBrancmng
3.1PolynomialGreatestCommonDivisors
3.2*LocalAnalysisoftheKnuth-Sch6nhageAlgorithm
3.3EvaluationandInterpolation
3.4*FastPointLocationinArrangementsofHyperplanes
3.5*Vapnik-ChervonenkisDimensionandEpsilon-Nets
3.6Exercises
3.7OpenProblems
3.8Notes
PartII.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
PartIII.HighDegree
Chapter8.TheDegreeBound
8.1AFieldTheoreticVersionoftheDegreeBound
8.2GeometricDegreeandaB6zoutInequality
8.3TheDegreeBound
8.4Applications
8.5*EstimatesfortheDegree
8.6*TheCaseofaFiniteField
8.7Exercises
8.8OpenProblems
8.9Notes
Chapter9.SpecificPolynomialswhichAreHardtoCompute
9.1AGenericComputation
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.1*EstimationoftheNumberofConnectedComponents
11.2LowerBoundsbytheNumberofConnectedComponents
11.3KnapsackandApplicationstoComputationalGeometry
11.4Exercises..
11.5OpenProblems
I1.6Notes
Chapter12.AdditiveComplexity
12.1Introduction
12.2*RealRootsofSparseSystemsofEquations
12.3ABoundontheAdditiveComplexity
12.4Exercises
12.5OpenProblems
12.6Notes
PartIV.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.6*TheSemiringT
14.7Exercises
14.8OpenProblems
14.9Notes
Chapter15.AsymptoticComplexityofMatrixMultiplication
15.1TheExponentofMatrixMultiplication
15.2FirstEstimatesoftheExponent
15.3ScalarRestrictionandExtension
15.4DegenerationandBorderRank
15.5TheAsymptoticSumInequality
15.6FirstStepsTowardstheLaserMethod
15.7*TightSets
15.8TheLaserMethod
15.9*PartialMatrixMultiplication
15.10*RapidMultiplicationofRectangularMatrices
15.11Exercises
15.12OpenProblems
15.13Notes
Chapter16.ProblemsRelatedtoMatrixMultiplication
16.1ExponentofProblems
16.2TriangularInversion
16.3LUP-decomposition
16.4MatrixInversionandDeterminant
16.5*TransformationtoEchelonForm
16.6*TheCharacteristicPolynomial
16.7*ComputingaBasisfortheKernel
16.8*OrthogonalBasisTransform
16.9*MatrixMultiplicationandGraphTheory
16.10Exercises
16.11OpenProblems
16.12Notes
Chapter17.LowerBoundsfortheComplexityofAlgebras
17.1FirstStepsTowardsLowerBounds
17.2MultiplicativeComplexityofAssociativeAlgebras
17.3*MultiplicativeComplexityofDivisionAlgebras
17.4*CommutativeAlgebrasofMinimalRank
17.5Exercises
17.6OpenProblems
17.7Notes
Chapter18.RankoverFiniteFieldsandCodes
18.1LinearBlockCodes
18.2LinearCodesandRank
18.3PolynomialMultiplicationoverFiniteFields
18.4*MatrixMultiplicationoverFiniteFields
18.5*RankofFiniteFields
18.6Exercises
18.7OpenProblems
18.8Notes
Chapter19.Rankof2-Sliceand3-SliceTensors
19.1TheWeierstraB-KroneckerTheory
19.2Rankof2-SliceTensors
19.3*Rankof3-SliceTensors
19.4Exercises
19.5Notes
Chapter20.TypicalTensorialRank
20.1GeometricDescription
20.2UpperBoundsontheTypicalRank
20.3*DimensionofConfigurationsinFormats
20.4Exercises
20.5OpenProblems
20.6*Appendix:TopologicalDegeneration
20.7Notes
PartV.CompleteProblems
Chapter21.PVersusNP:ANonuniformAlgebraicAnalogue
21.1Cook'sVersusValiant'sHypothesis
21.2p-DefinabilityandExpressionSize
21.3UniversalityoftheDeterminant
21.4CompletenessofthePermanent
21.5*TheExtendedValiantHypothesis
21.6Exercises
21.7OpenProblems
21.8Notes
Bibliography
ListofNotation
Index...