Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

ISSN 1088-9485(online) ISSN 0273-0979(print)



The fundamental theorem of algebra and complexity theory

Author: Steve Smale
Journal: Bull. Amer. Math. Soc. 4 (1981), 1-36
MSC (1980): Primary 00-02, 12D10, 68C25, 65H05, 58-02; Secondary 01A05, 30D10
MathSciNet review: 590817
Full-text PDF Free Access

References | Similar Articles | Additional Information

References [Enhancements On Off] (What's this?)

  • 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
  • L. E. J. Brouwer, 1924 (w. B. de Loor), Intuitionischer Beweis des Fundamentalsatzes der Algebra, Coll. Works, vol. 1 (1975), North-Holland, Amsterdam.
  • G. E. Collins, Infallible calculation of polynomial zeros to specified precision, Mathematical software, III (Proc. Sympos., Math. Res. Center, Univ. Wisconsin, Madison, Wis., 1977) Academic Press, New York, 1977, pp. 35–68. Publ. Math. Res. Center, No. 39. MR 0474768
  • G. Debreu, 1959, Theory of value, Yale Univ. Press, New Haven, Conn.
  • 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
  • H. Eves, 1976, An introduction to the history of mathematics (4th ed.), Holt, Rinehart and Winston, New York.
  • Michael R. Garey and David S. Johnson, Computers and intractability, W. H. Freeman and Co., San Francisco, Calif., 1979. A guide to the theory of NP-completeness; A Series of Books in the Mathematical Sciences. MR 519066
  • C. F. Gauss, 1973, Werke, Band X, Georg Olms Verlag, New York.
  • 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 Co., 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
  • 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
  • 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
  • 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
  • Wilfred Kaplan, Ordinary differential equations, Addison-Wesley Series in Systems Engineering, (Available in U.S.A. and Canada from) Addison-Wesley Publishing Co., Inc., Reading, Mass., 1958. MR 0103305
  • James A. Jenkins, Univalent functions and conformal mapping, Ergebnisse der Mathematik und ihrer Grenzgebiete, (N.F.), Heft 18, Springer-Verlag, Berlin-Göttingen-Heidelberg, 1958. Reihe: Moderne Funktionentheorie. 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
  • 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
  • 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, Academic Press [A Subsidiary of Harcourt Brace Jovanovich, Publishers], New York-London, 1973. Third edition of Solution of equations and systems of equations; Pure and Applied Mathematics, Vol. 9. MR 0359306
  • Jean-Claude Pont, La topologie algébrique des origines à Poincaré, Presses Universitaires de France, Paris, 1974 (French). Préface de René Taton; Thèse No. 4706; Présentée à l’École Polytechnique Fédérale Zurich pour l’obtention du titre de Docteur ès sciences mathématiques; Bibliothèque de Philosophie Contemporaine. MR 0472374
  • Luis A. Santaló, Integral geometry and geometric probability, Addison-Wesley Publishing Co., Reading, Mass.-London-Amsterdam, 1976. With a foreword by Mark Kac; Encyclopedia of Mathematics and its Applications, Vol. 1. MR 0433364
  • Herbert Scarf, The computation of economic equilibria, Yale University Press, New Haven, Conn.-London, 1973. With the collaboration of Terje Hansen; Cowles Foundation Monograph, No. 24. 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), Springer, Berlin, 1975, pp. 287–292. Lecture Notes in Math., Vol. 468. 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
  • 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) North-Holland Publishing Co., Amsterdam, 1977, pp. 191–205. Contributions to Economic Analysis, Vol. 105. MR 0459553
  • D. Smith, 1953, History of mathematics, vol. II, Dover, New York.
  • 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 [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. MR 0395140
  • B. Van der Waerden, 1953, Modern algebra, Vol. I, Ungar, New York.
  • 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
  • H. Weyl, Randbemerkungen zu Hauptproblemen der Mathematik, Math. Z. 20 (1924), no. 1, 131–150 (German). MR 1544667, DOI
  • Hermann Weyl, On the Volume of Tubes, Amer. J. Math. 61 (1939), no. 2, 461–472. MR 1507388, DOI
  • 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

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1980): 00-02, 12D10, 68C25, 65H05, 58-02, 01A05, 30D10

Retrieve articles in all journals with MSC (1980): 00-02, 12D10, 68C25, 65H05, 58-02, 01A05, 30D10

Additional Information