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

Blum, Lenore; Shub, Mike; Smale, Steve

doi:10.1090/S0273-0979-1989-15750-9

On a theory of computation and complexity over the real numbers: $NP$- completeness, recursive functions and universal machines
HTML articles powered by AMS MathViewer

by Lenore Blum, Mike Shub and Steve Smale PDF

Bull. Amer. Math. Soc. 21 (1989), 1-46

References

A. Aho, Dž. Hopkroft, and Dž. Ul′man, Postroenie i analiz vychislitel′nykh algoritmov, “Mir”, Moscow; distributed by Imported Publications, Chicago, Ill., 1979 (Russian). Translated by A. O. Slisenko; Edited by Ju. V. Matijasevič. MR 538444
Eberhard Becker, On the real spectrum of a ring and its application to semialgebraic geometry, Bull. Amer. Math. Soc. (N.S.) 15 (1986), no. 1, 19–60. MR 838786, DOI 10.1090/S0273-0979-1986-15431-5
Paul Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), no. 1, 85–141. MR 741725, DOI 10.1090/S0273-0979-1984-15240-6
A. Borodin, Structured vs. general models in computational complexity, Logic and algorithmic (Zurich, 1980) Monograph. Enseign. Math., vol. 30, Univ. Genève, Geneva, 1982, pp. 47–65. MR 648295
Hans Brolin, Invariant sets under iteration of rational functions, Ark. Mat. 6 (1965), 103–144 (1965). MR 194595, DOI 10.1007/BF02591353
Nigel Cutland, Computability, Cambridge University Press, Cambridge-New York, 1980. An introduction to recursive function theory. MR 572788
Martin Davis, Computability, Courant Institute of Mathematical Sciences, New York University, New York, 1974. Notes by Barry Jacobs from lectures given during 1973-1974. MR 0347574
Martin Davis, Yuri Matijasevič, and Julia Robinson, Hilbert’s tenth problem: Diophantine equations: positive aspects of a negative solution, Mathematical developments arising from Hilbert problems (Proc. Sympos. Pure Math., Northern Illinois Univ., De Kalb, Ill., 1974) Amer. Math. Soc., Providence, R.I., 1976, pp. 323–378. (loose erratum). MR 0432534
Martin Davis and Hilary Putnam, Diophantine sets over polynomial rings, Illinois J. Math. 7 (1963), 251–256. MR 147387
J. Denef, Diophantine sets over $\textbf {Z}[T]$, Proc. Amer. Math. Soc. 69 (1978), no. 1, 148–150. MR 462934, DOI 10.1090/S0002-9939-1978-0462934-X
J. Denef, The Diophantine problem for polynomial rings and fields of rational functions, Trans. Amer. Math. Soc. 242 , posted on (1978), 391–399. MR 0491583, DOI 10.1090/S0002-9947-1978-0491583-7
Samuel Eilenberg, Automata, languages, and machines. Vol. A, Pure and Applied Mathematics, Vol. 58, Academic Press [Harcourt Brace Jovanovich, Publishers], New York, 1974. MR 0530382
Erwin Engeler, Algorithmic approximations, J. Comput. System Sci. 5 (1971), 67–82. MR 293874, DOI 10.1016/S0022-0000(71)80008-9
Harvey Friedman, Algorithmic procedures, generalized Turing algorithms, and elementary recursion theory, Logic Colloquium ’69 (Proc. Summer School and Colloq., Manchester, 1969) North-Holland, Amsterdam, 1971, pp. 361–389. MR 0304140
Ker-I Ko and Harvey Friedman, Computational complexity of real functions, Theoret. Comput. Sci. 20 (1982), no. 3, 323–352. MR 666209, DOI 10.1016/S0304-3975(82)80003-0
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
D. Yu. Grigor′ev and N. N. Vorobjov Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), no. 1-2, 37–64. MR 949112, DOI 10.1016/S0747-7171(88)80005-1
L. A. Harrington, M. D. Morley, and S. G. Simpson (eds.), Harvey Friedman’s research on the foundations of mathematics, Studies in Logic and the Foundations of Mathematics, vol. 117, North-Holland Publishing Co., Amsterdam, 1985. MR 835250
Gabor T. Herman and Stephen D. Isard, Computability over arbitrary fields, J. London Math. Soc. (2) 2 (1970), 71–79. MR 249298, DOI 10.1112/jlms/s2-2.1.73
J. P. Jones and Y. V. Matijasevič, Register machine proof of the theorem on exponential Diophantine representation of enumerable sets, J. Symbolic Logic 49 (1984), no. 3, 818–829. MR 758933, DOI 10.2307/2274135
Myong-Hi Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331–344. MR 1018023, DOI 10.1016/0885-064X(89)90029-0
László Lovász, An algorithmic theory of numbers, graphs and convexity, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 50, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, PA, 1986. MR 861822, DOI 10.1137/1.9781611970203
Michael Machtey and Paul Young, An introduction to the general theory of algorithms, The Computer Science Library: Theory of Computation Series, North-Holland, New York-Oxford-Shannon, 1978. MR 0483344
Yu. I. Manin, A course in mathematical logic, Graduate Texts in Mathematics, Vol. 53, Springer-Verlag, New York-Berlin, 1977. Translated from the Russian by Neal Koblitz. MR 0457126, DOI 10.1007/978-1-4757-4385-2
Zohar Manna, Mathematical theory of computation, McGraw-Hill Computer Science Series, McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. MR 0400771
Barry Mazur, Arithmetic on curves, Bull. Amer. Math. Soc. (N.S.) 14 (1986), no. 2, 207–259. MR 828821, DOI 10.1090/S0273-0979-1986-15430-3
J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275–280. MR 161339, DOI 10.1090/S0002-9939-1964-0161339-9
Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall Series in Automatic Computation, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. MR 0356580
Marian Boykan Pour-El and Ian Richards, Computability and noncomputability in classical analysis, Trans. Amer. Math. Soc. 275 (1983), no. 2, 539–560. MR 682717, DOI 10.1090/S0002-9947-1983-0682717-1
Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. MR 805539, DOI 10.1007/978-1-4612-1098-6
Michael O. Rabin, Computable algebra, general theory and theory of computable fields, Trans. Amer. Math. Soc. 95 (1960), 341–360. MR 113807, DOI 10.1090/S0002-9947-1960-0113807-4
Michael O. Rabin, Proving simultaneous positivity of linear forms, J. Comput. System Sci. 6 (1972), 639–650. MR 451858, DOI 10.1016/S0022-0000(72)80034-5
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462
Adi Shamir, Factoring numbers in $O(\textrm {log}\,n)$ arithmetic steps, Inform. Process. Lett. 8 (1979), no. 1, 28–31. MR 515509, DOI 10.1016/0020-0190(79)90087-5
J. C. Shepherdson and H. E. Sturgis, Computability of recursive functions, J. Assoc. Comput. Mach. 10 (1963), 217–255. MR 151374, DOI 10.1145/321160.321170
Arnold Schönhage, On the power of random access machines, Automata, languages and programming (Sixth Colloq., Graz, 1979) Lecture Notes in Comput. Sci., vol. 71, Springer, Berlin, 1979, pp. 520–529. MR 573259, DOI 10.1007/3-540-09510-1_{4}2
Steve Smale, On the topology of algorithms. I, J. Complexity 3 (1987), no. 2, 81–89. MR 907191, DOI 10.1016/0885-064X(87)90021-5
Eduardo D. Sontag, Polynomial response maps, Lecture Notes in Control and Information Sciences, vol. 13, Springer-Verlag, Berlin-New York, 1979. MR 541302, DOI 10.1007/BFb0042025
J. Michael Steele and Andrew C. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), no. 1, 1–8. MR 646886, DOI 10.1016/0196-6774(82)90002-5
Volker Strassen, Algebraische Berechnungskomplexität, Perspectives in mathematics, Birkhäuser, Basel, 1984, pp. 509–550 (German). MR 779688
Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley-Los Angeles, Calif., 1951. 2nd ed. MR 0044472, DOI 10.1525/9780520348097
René Thom, Sur l’homologie des variétés algébriques réelles, Differential and Combinatorial Topology (A Symposium in Honor of Marston Morse), Princeton Univ. Press, Princeton, N.J., 1965, pp. 255–265 (French). MR 0200942
J. Tiuryn, A survey of the logic of effective definitions, Logic of programs (Zürich, 1979) Lecture Notes in Comput. Sci., vol. 125, Springer, Berlin, 1981, pp. 198–245. MR 735280, DOI 10.1007/3-540-11160-3_{7}
J. F. Traub and H. Woźniakowski, Complexity of linear programming, Oper. Res. Lett. 1 (1981/82), no. 2, 59–62. MR 669863, DOI 10.1016/0167-6377(82)90047-5
L. G. Valiant, Completeness classes in algebra, Conference Record of the Eleventh Annual ACM Symposium on Theory of Computing (Atlanta, Ga., 1979) ACM, New York, 1979, pp. 249–261. MR 564634
Lou van den Dries, Alfred Tarski’s elimination theory for real closed fields, J. Symbolic Logic 53 (1988), no. 1, 7–19. MR 929371, DOI 10.2307/2274424
Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science, Vol. 3, Annual Reviews, Palo Alto, CA, 1988, pp. 317–347. MR 1001207
Shmuel Winograd, Arithmetic complexity of computations, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 33, Society for Industrial and Applied Mathematics (SIAM), Philadelphia, Pa., 1980. MR 565260, DOI 10.1137/1.9781611970364