The Collected Papers of Stephen Smale

The following sections are included:

• Contents

The following sections are included:

• Appendix: Personal Reminiscences by Mike Shub

• References

The following sections are included:

• The P vs. NP problem

• Solving equations

• Additional remarks

• References

The following sections are included:

• Introduction

• The Curves C(x) and Existence of Zeroes

• An Algorithm

• Polynomial Examples

• Convergent Algorithms

• A Practical Algorithm

• A Sure-Fire Algorithm

• Other Sure-Fire Algorithms

• Bibliography

The following sections are included:

• PART I

• PART II

• PART III

• References

The following sections are included:

• Section 1

• Section 2

• Section 3

• Section 4

• Section 5

• REFERENCES

The following sections are included:

• CHAPTER I
  • Introduction
  • On efficient zero-finding
  • On the efficiency of linear programming
  • On well-posed linear systems
  • On efficient approximation of integrals

• CHAPTER II
  • Convergence of Newton's method
  • A short elementary proof of the fundamental theorem of algebra and the topology of polynomials
  • Fast convergence of Newton's method
  • Purely iterative algorithms
  • Proof of Theorem A
  • What is an algorithm?

• CHAPTER III
  • Proof of Theorem D
  • Questions of precision

• References

This paper deals with traditional algorithms, Newton's method and a higher order generalization due to Euler. These iterations schemes and their Modifications have had a great success in solving nonlinear systems of equations. We give some understanding of this phenomenon by giving estimates of efficiency. The problem we focus on is that of finding a zero of a complex polynomial.

Please refer to full text.

The following sections are included:

• Section 1

• Section 2

• Section 3

• Section 4

• Acknowledgment

• References

Please refer to full text.

The main goal of this work is an attempt to understand the efficiency of algorithms for solving systems of equations. For example, consider a map f from complex Cartesian space Cⁿ to Cⁿ given by polynomials. How fast can one find good approximations to one or all of the zeros of f? However, for clarity of exposition and development we will usually swing from one extreme to another about this example, proving theorems on one hand for a single complex polynomial and on the other hand for an analytic map f: F → F from one Banach space to another (both real or both complex)…

Isaac Newton made a continuous mathematical model of a discrete universe using differential equations to explain how things in that universe move. Mathematicians can look at the computer today in the same way that Newton looked at the world in the seventeenth century to gain some understanding of “the machine.” One can try to understand die computer in a way similar to the way a physicist understands the world, a different way from the engineers' approach. In order to understand the laws of computation one can design a mathematical model using continuous mathematics and calculus to lead to a deeper understanding of the process of computation…

We present a model for computation over the reals or an arbitrary (ordered) ring R. In this general setting, we obtain universal machines, partial recursive functions, as well as NP-complete problems. While our theory reflects the classical over Z (e.g., the computable functions are the recursive functions) it also reflects the special mathematical character of the underlying ring R (e.g., complements of Julia sets provide natural examples of R. E. undecidable sets over the reals) and provides a natural setting for studying foundational issues concerning algorithms in numerical analysis.

The problem of increasing the understanding of algorithms by considering the foundations of numerical analysis and computer science is considered. The schism between scientific computing and computer science is discussed from a theoretical perspective. These theoretical considerations have an intellectual importance when viewing the computer. In particular, the legitimacy and importance of models of machines that accept real numbers is considered.

The reason for a theory of computation, for me in particular, comes from an attempt to understand algorithms in a more systematic way. The notion of algorithm is very old in mathematics; it goes back a couple of thousand years. Mathematicians have talked about algorithms for a long time, but it was not until Gödel that they tried to formalize the notion of algorithm. In Gödel's incompleteness theorem one saw for the first time the limitations of computations or the need to study more clearly what could be done…

The following sections are included:

• THE MAIN RESULT AND THE STRUCTURE OF ITS PROOF
  • Introduction
  • Complexity of path following in Banach spaces
  • Complexity for polynomial systems in terms of the condition number, μ
  • Complexity in terms of the distance to the discriminant variety Σ

• THE ABSTRACT THEORY
  • Point Estimates
  • The domination theorem
  • Robustness

• REDUCTION TO THE ANALYSIS OF THE CONDITION NUMBER
  • The higher derivative estimate
  • Analysis of projective Newton method

• CHARACTERIZING THE CONDITION NUMBER
  • The projective case μ = 1/ρ
  • Bounds on zeros and the affine case

• References

In this paper we study volume estimates in the space of systems of n homegeneous polynomial equations of fixed degrees d_i with respect to a natural Hermitian structure on the space of such systems invariant under the action of the unitary group. We show that the average number of real roots of real systems is where , is the Bezout number. We estimate the volume of the subspace of badly conditioned problems and show that volume is bounded by a small degree polynomial in n, N and times the reciprocal of the condition number to the fourth power. Here N is the dimension of the space of systems.

The following sections are included:

• Introduction

• Elliptic Fekete Polynomials Are Well Conditioned

• Proof of Propositions 1 and 2

• References

We estimate the probability that a given number of projective Newton steps applied to a linear homotopy of a system of n homogeneous polynomial equations in n + 1 complex variables of fixed degrees will find all the roots of the system. We also extend the framework of our analysis to cover the classical implicit function theorem and revisit the condition number in this context. Further complexity theory is developed.

Shub, M. and S. Smale, Complexity of Bezout's theorem V: Polynomial time, Theoretical Computer Science 133 (1994) 141–164.

We show that there are algorithms which find an approximate zero of a system of polynomial equations and which function in polynomial time on the average. The number of arithmetic operations is cN^4s, where N is the input size and c a universal constant.

The following sections are included:

• Introduction

• Background

• Decidability: Proof of Proposition A

• Definability: Proof of Proposition B

• Incompleteness

• Decidability over R and Property D

• On the Undecidability of the Mandelbrot Set over R

• References

Cucker, F., M. Shub and S. Smale, Separation of complexity classes in Koiran's weak model, Theoretical Computer Science 133 (1994) 3–14.

We continue the study of complexity classes over the weak model introduced by P. Koiran. In particular we provide several separations of complexity classes, the most remarkable being the strict inclusion of P in NP. Other separations concern classes defined by weak polynomial time over parallel or alternating machines as well as over nondeterministic machines whose guesses are required to be 0 or 1.

The following sections are included:

• Section 1. Introduction

• Section 2. Proof of Theorem 1 (of Section 1)

• Section 3. Easy to compute sequences in rings

• Section 4. Proof of Theorem 2 (of Section 1)

• REFERENCES

Finding a natural meeting ground between the highly developed complexity theory of computer science — with its historical roots in logic and the discrete mathematics of the integers — and the traditional domain of real computation, the more eclectic less foundational field of numerical analysis — with its rich history and longstanding traditions in the continuous mathematics of analysis — presents a compelling challenge. Here we illustrate the issues and pose our perspective toward resolution.

When complexity theory is studied over an arbitrary unordered field K, the classical theory is recaptured with K = ℤ₂. The fundamental result that the Hilbert Nullstellensatz as a decision problem is NP-complete over K allows us to reformulate and investigate complexity questions within an algebraic framework and to develop transfer principles for complexity theory.

Here we show that over algebraically closed fields K of characteristic 0 the fundamental problem “P ≠ NP?” has a single answer that depends on the tractability of the Hilbert Nullstellensatz over the complex numbers ℂ. A key component of the proof is the Witness Theorem enabling the elimination of transcendental constants in polynomial time.

The following sections are included:

• Preface

• Introduction

• Fundamental theorem of algebra

• Condition numbers

• Newton's method and point estimates

• Linear algebra
  • Linear systems
  • Eigenvalue problems

• Complexity in many variables

• Probabilistic estimates

• Real machines

• Some other directions

• REFERENCES

The following sections are included:

• INTRODUCTION AND MAIN RESULTS

• PROOFS OF THEOREMS 1 AND 2

• REFERENCES

We exhibit an algorithm computing, for a polynomial f ∊ ℤ[t], the set of its integer roots. The running time of the algorithm is polynomial in the size of the sparse encoding of f.

This paper has two agendas. One is to develop the foundations of round-off in computation. The other is to describe an algorithm for deciding feasibility for polynomial systems of equations and inequalities together with its complexity analysis and its round-off properties. Each role reinforces the other.

Categories and Subject Descriptors: F.2.1 [Analysis of Algorithms and Problem Complexity]: Numerical Algorithms and Problems; G 5 [Numerical Analysis]: Roots of Nonlinear Equations

General Terms: Algorithms, Theory