Remote Access Bulletin of the American Mathematical Society

Bulletin of the American Mathematical Society

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



On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines

Authors: Lenore Blum, Mike Shub and Steve Smale
Journal: Bull. Amer. Math. Soc. 21 (1989), 1-46
MSC (1985): Primary 03D15, 68Q15; Secondary 65V05
MathSciNet review: 974426
Full-text PDF

References | Similar Articles | Additional Information

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

  • F. Abramson, Effective computation over the real numbers, Proceedings of the 12th Annual (IEEE) Symposium on Switching and Automata Theory, 1971, pp. 33-37.
  • A. Aho, J. Hopcroft, and J. Ullman, The design and analysis of computer algorithms, Addison-Wesley, Reading, Mass., 1979. MR 538444
  • E. Becker, On the real spectrum of a ring and its application to semialgebraic geometry, Bull. Amer. Math. Soc. (N.S.) 15 (1986), 19-60. MR 838786
  • M. Ben-Or, Lower bounds for algebraic computation trees, Proceedings 15th ACM STOC, 1983, pp. 80-86.
  • P. Blanchard, Complex analytic dynamics of the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), 85-141. MR 741725
  • A. Borodin, Structured vs. general models in computational complexity, Logic and Algorithmic, Monographie, no. 30, de L'enseignement Mathematique, Geneva, 1982, pp. 47-65. MR 648295
  • H. Brolin, Invariant sets under iteration of rational functions, Ark. Mat. 6 (1965) 103-144. MR 194595
  • J. Canny, Some algebraic and geometric computations in PSPACE, 20th Annual ACM Symposium on Theory of Computing, 1988, pp. 460-467.
  • S. A. Cook, The complexity of theorem proving procedures, Proceedings 3rd ACM STOC 1971, pp. 151-158.
  • N. Cutland, Computability, Cambridge Univ. Press, Cambridge, 1980. MR 572788
  • M. Davis, Computability and unsolvability, Dover, New York, 1982. MR 347574
  • M. Davis, Y. Matijasevic, and J. Robinson, Hilbert's tenth Problem. Diophantine equations: positive aspects of a negative solution, Mathematical Development Arising from Hilbert Problems, Proc. Sympos. Pure Math., vol. 28, Amer. Math. Soc. Providence, R.I., 1976, pp. 323-378. MR 432534
  • M. Davis, and H. Putnam, Diophantine sets over polynomial rings. III, J. Math. 7 (1963), 251-256. MR 147387
  • J. Denef, 1, Diophantine sets over Z[T], Proc. Amer. Math. Soc. 69 (1978), 148-150. MR 462934
  • J. Denef, 2, The Diophantine problem for polynomial rings and fields of rational functions, Trans. Amer. Math. Soc. 242 (1978), 391-399. MR 491583
  • B. C. Eaves and U. G. Rothblum, A theory on extending algorithms for parametric problems, Department of O.R., Stanford Univ., 1985.
  • S. Eilenberg, Automata, languages, and machines, vol. A, Academic Press, New York, 1974. MR 530382
  • E. Engeler, Algorithmic approximations, J. Comput. System Sci. 5 (1971), 67-82. MR 293874
  • H. Friedman, Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, Logic Colloquium 1969, (R. O. Gandy and Yates, eds.) C.M.E., North-Holland, Amsterdam, 1971, pp. 361-390. MR 304140
  • H. Friedman and K. Ko, Computational complexity of real functions, J. Theoret. Comput. Sci. 20 (1982), 323-352. MR 666209
  • N. Friedman, Some results on the effects of arithmetic comparisons, Proceedings of the 13th Annual (IEEE) Symposium on Switching and Automata Theory, 1972, pp. 139-143.
  • M. Garey and D. Johnson, Computers and intractability, Freeman, New York, 1979. MR 519066
  • D. Y. Grigorev and N. N. Vorobojov, Solving systems of polynomial inequalities in subexponential time, J. Symbolic Computation, 5 nos. 1 and 2 (1988), 37-64. MR 949112
  • L. Harrington, M. Morley, A. Seedrov, and S. Simpson (eds.), Harvey Friedman's Research on the Foundations of Mathematics, North-Holland, Amsterdam, 1985. MR 835250
  • G. T. Herman and S. D. Isard, Computability over arbitrary fields, J. London Math. Soc. (2) 2 (1970), 73-79. MR 249298
  • H. J. Hoover, Feasibly constructive analysis, Ph.D. Thesis, Department of Computer Science, Univ. of Toronto, 1987.
  • J. P. Jones and Y. V. Matijasevic, Register machine proof of the theorem on exponential diophantine representation of enumerable sets, J. Symbolic Logic 49 (1984), 818-829. MR 758933
  • M. H. Kim, Topological complexity of a root finding algorithm, preprint. MR 1018023
  • C. Kreitz and K. Weihrauch, Complexity theory on real numbers and functions, Lecture Notes in Computer Sci., 145, Theoretical Computer Science, (A. B. Cremers and H. P. Kreigel eds.), Springer-Verlag, Berlin and New York, 1982, pp. 165-174.
  • L. Lovász, An algorithmic theory of numbers, graphs and complexity, CBMS-NSF Series 50, SIAM, Phil., Pa, 1986. MR 861822
  • M. Machtey and P. Young, An introduction to the general theory of algorithms, North-Holland, New York, 1978. MR 483344
  • X. I. Manin, A course in mathematical logic, Springer-Verlag, Berlin and New York, 1977; 1984 (2nd printing). MR 457126
  • Z. Manna, Mathematical theory of computation, McGraw-Hill, New York, 1974. MR 400771
  • B. Mazur, Arithmetic on curves, Bull. Amer. Math. Soc. (N.S.) 14 (1986), 207-259. MR 828821
  • J. Milnor, On the Betti-numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275-280. MR 161339
  • M. Minsky, Computation: Finite and infinite machines, Prentice-Hall, Englewood Cliffs, New Jersey, 1967. MR 356580
  • Y. N. Moschovakis, Foundations of the theory of algorithms. I, draft 1986.
  • V. Ya Pan, Methods of computing values of polynomials, Russian Math. Surveys 21 no. 1 (1966), 105-136.
  • M. B. Pour-El and I. Richards, Computability and noncomputability in classical analysis, Trans. Amer. Math. Soc. 275 (1983), 539-560. MR 682717
  • F. P. Preparata and M. I. Shamos, Computational geometry, Springer-Verlag, Berlin and New York, 1985. MR 805539
  • M. Rabin, 0.1, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341-360. MR 113807
  • M. Rabin, 0.2, Proving simultaneous positivity of linear forms, J. Comput. and System Sci. 6(1972), 639-650. MR 451858
  • J. Renegar, A faster PSPACE algorithm for deciding the existential theory of the reals, Technical Report No. 792, School of Operations Research and Industrial Engineering, Cornell, April 1988. (Also, Proceedings of the 29th Annual Symposium on Foundations of Computer Science, 1988, pp. 291-295.)
  • H. Rogers, Jr., Theory of recursive functions and effective computability, McGraw-Hill, New York, 1967. MR 224462
  • A. Shamir, Factoring numbers in O(log n) arithmetic steps, Inform. Process. Lett. 8 no. 1 (1979), 28-31. MR 515509
  • J. C. Shepherdson and H. E. Sturgis, Computability of recursive functions, J. Assoc. Comput. Mach. 10 (1963), 217-255. MR 151374
  • A. Schönhage, On the power of random access machines, Proc. 6th ICALP, Lecture Notes in Computer Science, no. 71, Springer-Verlag, Berlin and New York, 1979, pp. 520-529. MR 573259
  • S. Smale, On the topology of algorithms. I, J. Complexity 3 (1987), 81-89. MR 907191
  • E. Sontag, Polynomial response maps, Lecture Notes in Control and Information Sciences, Springer-Verlag, Berlin and New York, 1979. MR 541302
  • M. Steele and A. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), 1-8. MR 646886
  • V. Strassen, Algebraische berechnungskomplexität, Perspectives in Mathematics, (Basel), Birkhäuser-Verlag, 1984. MR 779688
  • D. Sullivan, Quasi-conformal homomorphisms and dynamics. III, IHES preprint.
  • A. Tarski, A decision method for elementary algebra and geometry, 2nd ed., Berkeley and Los Angeles, 1951, vol. 1, 63 pp. MR 44472
  • R. Thom, Sur l'homologie des variétés algébriques réelles, Differential and Combinatorial Topology, Princeton Univ. Press, Princeton, New Jersey, 1965, pp. 255-265. MR 200942
  • J. Tiuryn, A survey of the logic of effective definitions, Lecture Notes in Computer Sci., 125, Logic of Programs, (E. Engeler, ed.), Springer-Verlag, Berlin New York, 1979, pp. 198-245. MR 735280
  • J. F. Traub and H. Wozniakowski, Complexity of linear programming, Oper. Res. Lett. 1 no. 2, (1982), 59-62. MR 669863
  • L. Valiant, Completeness classes in algebra, Proc. 11th Ann ACM STOC, 1979, pp. 249-261. MR 564634
  • L. van den Dries, Alfred Tarski's elimination theory for real closed fields, J. Symbolic Logic 1 (1988), 7-19. MR 929371
  • J. von zur Gathen, Algebraic complexity theory, Technical Report No. 207/88, Department of Computer Science, University of Toronto, January 1988, 37 pp. MR 1001207
  • S. Winograd, Arithmetic complexity of computations, SIAM Regional Conf. Ser. Appl. Math. 33 (1980), 93pp. MR 565260

Similar Articles

Retrieve articles in Bulletin of the American Mathematical Society with MSC (1985): 03D15, 68Q15, 65V05

Retrieve articles in all journals with MSC (1985): 03D15, 68Q15, 65V05

Additional Information


American Mathematical Society