The fundamental theorem of algebra and complexity theory

Smale, Steve

doi:10.1090/S0273-0979-1981-14858-8

The fundamental theorem of algebra and complexity theory
HTML articles powered by AMS MathViewer

by Steve Smale PDF

Bull. Amer. Math. Soc. 4 (1981), 1-36

References

Béla Barna, Über die Divergenzpunkte des Newtonschen Verfahrens zur Bestimmung von Wurzeln algebraischen Gleichungen. II, Publ. Math. Debrecen 4 (1956), 384–397 (German). MR 78956
G. E. Collins, Infallible calculation of polynomial zeros to specified precision, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Publ. Math. Res. Center, No. 39, Academic Press, New York, 1977, pp. 35–68. MR 0474768
Bruno Dejon and Peter Henrici (eds.), Constructive aspects of the fundamental theorem of algebra, Wiley-Interscience [A Division of John Wiley & Sons, Ltd.], London-New York-Sydney, 1969. MR 0253555
B. Curtis Eaves and Herbert Scarf, The solution of systems of piecewise linear equations, Math. Oper. Res. 1 (1976), no. 1, 1–27. MR 445792, DOI 10.1287/moor.1.1.1
Michael R. Garey and David S. Johnson, Computers and intractability, A Series of Books in the Mathematical Sciences, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness. MR 519066
Phillip A. Griffiths, Complex differential and integral geometry and curvature integrals associated to singularities of complex analytic varieties, Duke Math. J. 45 (1978), no. 3, 427–512. MR 507455
J. Hartmanis, Observations about the development of theoretical computer science, 20th Annual Symposium on Foundations of Computer Science (San Juan, Puerto Rico, 1979) IEEE, New York, 1979, pp. 224–233. MR 598111
W. K. Hayman, Multivalent functions, Cambridge Tracts in Mathematics and Mathematical Physics, No. 48, Cambridge University Press, Cambridge, 1958. MR 0108586
Peter Henrici, Applied and computational complex analysis. Vol. 2, Wiley-Interscience [John Wiley & Sons], New York-London-Sydney, 1977. Special functions—integral transforms—asymptotics—continued fractions. MR 0453984
Einar Hille, Analytic function theory. Vol. II, Introductions to Higher Mathematics, Ginn and Company, Boston, Mass.-New York-Toronto, Ont., 1962. MR 0201608
Morris W. Hirsch, A proof of the nonretractibility of a cell onto its boundary, Proc. Amer. Math. Soc. 14 (1963), 364–365. MR 145502, DOI 10.1090/S0002-9939-1963-0145502-8
Morris W. Hirsch and Stephen Smale, On algorithms for solving $f(x)=0$, Comm. Pure Appl. Math. 32 (1979), no. 3, 281–313. MR 517937, DOI 10.1002/cpa.3160320302
David A. Hoffman and Robert Osserman, The geometry of the generalized Gauss map, Mem. Amer. Math. Soc. 28 (1980), no. 236, iii+105. MR 587748, DOI 10.1090/memo/0236
Harold Hotelling, Tubes and Spheres in n-Spaces, and a Class of Statistical Problems, Amer. J. Math. 61 (1939), no. 2, 440–460. MR 1507387, DOI 10.2307/2371512
Wilfred Kaplan, Ordinary differential equations, Addison-Wesley Series in Systems Engineering, Addison-Wesley Publishing Co., Reading, Mass., 1958. (Available in U.S.A. and Canada from). MR 0103305
James A. Jenkins, Univalent functions and conformal mapping, Reihe: Moderne Funktionentheorie, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1958. MR 0096806
R. B. Kellogg, T. Y. Li, and J. Yorke, A constructive proof of the Brouwer fixed-point theorem and computational results, SIAM J. Numer. Anal. 13 (1976), no. 4, 473–483. MR 416010, DOI 10.1137/0713041
Imre Lakatos, Proofs and refutations, Cambridge University Press, Cambridge-New York-Melbourne, 1976. The logic of mathematical discovery; Edited by John Worrall and Elie Zahar. MR 0479916, DOI 10.1017/CBO9781139171472
Serge Lang, Algebra, Addison-Wesley Publishing Co., Inc., Reading, Mass., 1965. MR 0197234
Morris Marden, Geometry of polynomials, 2nd ed., Mathematical Surveys, No. 3, American Mathematical Society, Providence, R.I., 1966. MR 0225972
A. M. Ostrowski, Solution of equations in Euclidean and Banach spaces, Pure and Applied Mathematics, Vol. 9, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations. MR 0359306
Jean-Claude Pont, La topologie algébrique des origines à Poincaré, Thèse No. 4706, Presses Universitaires de France, Paris, 1974 (French). Préface de René Taton; Présentée à l’École Polytechnique Fédérale Zurich pour l’obtention du titre de Docteur ès sciences mathématiques. MR 0472374
Luis A. Santaló, Integral geometry and geometric probability, Encyclopedia of Mathematics and its Applications, Vol. 1, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac. MR 0433364
Herbert Scarf, The computation of economic equilibria, Cowles Foundation Monograph, No. 24, Yale University Press, New Haven, Conn.-London, 1973. With the collaboration of Terje Hansen. MR 0391909
Glenn Schober, Coefficient estimates for inverses of schlicht functions, Aspects of contemporary complex analysis (Proc. NATO Adv. Study Inst., Univ. Durham, Durham, 1979) Academic Press, London-New York, 1980, pp. 503–513. MR 623495
S. Smale, Sufficient conditions for an optimum, Dynamical systems—Warwick 1974 (Proc. Sympos. Appl. Topology and Dynamical Systems, Univ. Warwick, Coventry, 1973/1974; presented to E. C. Zeeman on his fiftieth birthday), Lecture Notes in Math., Vol. 468, Springer, Berlin, 1975, pp. 287–292. MR 0649781
Steve Smale, A convergent process of price adjustment and global Newton methods, J. Math. Econom. 3 (1976), no. 2, 107–120. MR 411577, DOI 10.1016/0304-4068(76)90019-7
Steve Smale, Convergent process of price adjustment and global Newton methods, Frontiers of quantitative economics, Vol. IIIA (Invited papers, Econometric Soc., Third World Congress, Toronto, Ont., 1975) Contributions to Economic Analysis, Vol. 105, North-Holland Publishing Co., Amsterdam, 1977, pp. 191–205. MR 0459553
D. J. Struik (ed.), A source book in mathematics, 1200–1800, Harvard University Press, Cambridge, Mass., 1969. MR 0238647
J. F. Traub (ed.), Analytic computational complexity, Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. MR 0395140
B. L. van der Waerden, Modern Algebra. Vol. I, Frederick Ungar Publishing Co., New York, N. Y., 1949. Translated from the second revised German edition by Fred Blum; With revisions and additions by the author. MR 0029363
Yieh Hei Wan, On local Pareto Optima, J. Math. Econom. 2 (1975), no. 1, 35–42. MR 401106, DOI 10.1016/0304-4068(75)90012-9
H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, Math. Z. 20 (1924), no. 1, 131–150 (German). MR 1544667, DOI 10.1007/BF01188076
Hermann Weyl, On the Volume of Tubes, Amer. J. Math. 61 (1939), no. 2, 461–472. MR 1507388, DOI 10.2307/2371513
Hassler Whitney, Complex analytic varieties, Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont., 1972. MR 0387634
J. H. Wilkinson, Rounding errors in algebraic processes, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1963. MR 0161456
Philip Wolfe, The “ellipsoid algorithm”, Science 208 (1980), no. 4441, 240–242. MR 565382, DOI 10.1287/mnsc.26.8.747