The Collected Papers of Stephen Smale

by Smale, Stephen; Cucker, Felipe; Wong, R.

• ISBN13: 9789810249939
• ISBN10: 9810249934
• Format: Hardcover
• Copyright: 2000-06-01
• Publisher: World Scientific Pub Co Inc

Table of Contents

Part VIII. Theory of Computation
On the Work of Steve Smale on the Theory of Computation	1035	(21)
M. Shub
The Work of Steve Smale on the Theory of Computation: 1990-1999	1056	(20)
L. Blum
F. Cucker
On Algorithms for Solving f(x)=0	1076	(32)
M. Hirsch
The fundamental Theorem of Algebra and Complexity Theory	1108	(36)
Computational Complexity: On the geometry of polynomials and a theory of cost, Part I	1144	(36)
M. Shub
On the Efficiency of Algorithms of Analysis	1180	(35)
Computational Complexity: On the Geometry of polynomials and a theory of cost, Part II	1215	(17)
M. Shub
On the Existence of Generally Convergent Algorithms	1232	(10)
M. Shub
Newton's Method Estimates form Data at One Point	1242	(12)
On the Topology of Algorithms, I.	1254	(9)
Algorithms for Solving Equations	1263	(24)
The Newtonian Contribution to Our Understanding of the Computer	1287	(6)
On a Theory of Computation and Complexity over the Real Numbers: NP-completeness, recursive functions and universal machines	1293	(46)
L. Blum
M. Shub
Some Remarks on the Foundations of Numerical Analysis	1339	(10)
Theory of Computation	1349	(10)
Complexity of Bezout's Theorem I: Geometric aspects	1359	(43)
M. Shub
Complexity of Bezout's Theorem II: Volumes and probabilities	1402	(19)
M. Shub
Complexity of Bezout's Theorem III: Condition number and packing	1421	(11)
M. Shub
Complexity of Bezout's Theorem IV: Probability of success: Extensions	1432	(21)
M. Shub
Complexity of Bezout's Theorem V: Polynomial time	1453	(24)
M. Shub
The Godel Incompleteness Theorem and Decidability over a Ring	1477	(19)
L. Blum
Separation of Complexity Classes in Koiran's Weak Model	1496	(12)
F. Cucker
2M. Shub
On the Intractability of Hilbert's Nullstellenstaz and an Algerbraic Version of ``NP≠P?''	1508	(8)
M. Shub
Complexity and Real Computation: A Manifesto	1516	(24)
L. Blum
F. Cucker
M. Shub
Algebraic Settings for the Problem ``P≠NP?''	1540	(20)
L. Blum
F. Cucker
M. Shub
Complexity Theory and Numerical Analysis	1560	(29)
Some Lower Bounds for the Complexity of Continuation Methods	1589	(12)
J.-P. Dedieu
A Polynomial Time algorithm for Diophantine Equations in One Variable	1601	(9)
F. Cucker
P. Koiran
Complexity Estimates Depending on Condition and Round-off Error	1610
F. Cucker