×

On a theory of computation and complexity over the real numbers: NP- completeness, recursive functions and universal machines. (English) Zbl 0681.03020

A model for computation over the reals \({\mathbb{R}}\) (or an arbitrary ordered ring \({\mathcal R})\) is presented. A machine over \({\mathcal R}\) is a digraph with two kinds of nodes: computation (fan-out 1) nodes labelled by polynomial maps \({\mathfrak g}: {\mathcal R}^ n\to {\mathcal R}^ n\), and branching (fan-out 2) nodes labelled by tests “\({\mathfrak h}(x)\geq 0''\) where \({\mathfrak h}: {\mathcal R}^ n\to {\mathcal R}\) are polynomials. The concepts of universal machine, recursive function and NP-completeness are introduced for such a model of machines. The theory obtained reflects the classical one over \({\mathbb{Z}}\), and captures the special mathematical character of the underlying ring \({\mathcal R}\). Specifically, it is shown that complements of Julia sets (a concept from dynamic system theory) provide natural examples of undecidable sets over the reals. An analogue of Cook’s NP-completeness theorem over the reals is also proved, and the 4-feasibility problem (i.e. the problem of deciding whether or not a real degree 4 polynomial has a zero) is shown to be NP-complete over \({\mathbb{R}}\). The paper is almost self-contained and provides a natural setting for the theory of algorithms and complexity in numerical analysis.
Reviewer: S.Yukna

MSC:

03D15 Complexity of computation (including implicit computational complexity)
03D10 Turing machines and related notions
03D20 Recursive functions and relations, subrecursive hierarchies
03D80 Applications of computability and recursion theory
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Построение и анализ вычислител\(^{\приме}\)ных алгоритмов, ”Мир”, Мосцощ; дистрибутед бы Импортед Публицатионс, Чицаго, Илл., 1979 (Руссиан). Транслатед бы А. О. Слисенко; Едитед бы Ју. В. Матијасевиč.
[2] 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. · Zbl 0634.14016
[3] Paul Blanchard, Complex analytic dynamics on the Riemann sphere, Bull. Amer. Math. Soc. (N.S.) 11 (1984), no. 1, 85 – 141. · Zbl 0558.58017
[4] 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. A. Borodin, Structured vs. general models in computational complexity, Enseign. Math. (2) 28 (1982), no. 3-4, 171 – 189.
[5] Hans Brolin, Invariant sets under iteration of rational functions, Ark. Mat. 6 (1965), 103 – 144 (1965). · Zbl 0127.03401 · doi:10.1007/BF02591353
[6] Nigel Cutland, Computability, Cambridge University Press, Cambridge-New York, 1980. An introduction to recursive function theory. · Zbl 0448.03029
[7] Martin Davis, Computability, Courant Institute of Mathematical Sciences, New York University, New York, 1974. Notes by Barry Jacobs from lectures given during 1973-1974. · Zbl 0080.00902
[8] 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., Vol. XXVIII, Northern Illinois Univ., De Kalb, Ill., 1974) Amer. Math. Soc., Providence, R. I., 1976, pp. 323 – 378. (loose erratum).
[9] Martin Davis and Hilary Putnam, Diophantine sets over polynomial rings, Illinois J. Math. 7 (1963), 251 – 256. · Zbl 0113.00604
[10] J. Denef, Diophantine sets over \?[\?], Proc. Amer. Math. Soc. 69 (1978), no. 1, 148 – 150. · Zbl 0393.03035
[11] J. Denef, The Diophantine problem for polynomial rings and fields of rational functions, Trans. Amer. Math. Soc. 242 , posted on (1978), 391 – 399. · Zbl 0399.10048
[12] Samuel Eilenberg, Automata, languages, and machines. Vol. A, Academic Press [A subsidiary of Harcourt Brace Jovanovich, Publishers], New York, 1974. Pure and Applied Mathematics, Vol. 58. Samuel Eilenberg, Automata, languages, and machines. Vol. B, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. With two chapters (”Depth decomposition theorem” and ”Complexity of semigroups and morphisms”) by Bret Tilson; Pure and Applied Mathematics, Vol. 59.
[13] Erwin Engeler, Algorithmic approximations, J. Comput. System Sci. 5 (1971), 67 – 82. · Zbl 0238.68016 · doi:10.1016/S0022-0000(71)80008-9
[14] 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.
[15] Ker-I Ko and Harvey Friedman, Computational complexity of real functions, Theoret. Comput. Sci. 20 (1982), no. 3, 323 – 352. · Zbl 0498.03047 · doi:10.1016/S0304-3975(82)80003-0
[16] 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. · Zbl 0411.68039
[17] D. Yu. Grigor\(^{\prime}\)ev and N. N. Vorobjov Jr., Solving systems of polynomial inequalities in subexponential time, J. Symbolic Comput. 5 (1988), no. 1-2, 37 – 64. · Zbl 0662.12001 · doi:10.1016/S0747-7171(88)80005-1
[18] L. A. Harrington, M. D. Morley, and S. G. Simpson , 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. · Zbl 0588.03001
[19] Gabor T. Herman and Stephen D. Isard, Computability over arbitrary fields, J. London Math. Soc. (2) 2 (1970), 71 – 79. · Zbl 0188.02502 · doi:10.1112/jlms/s2-2.1.73
[20] 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. · Zbl 0599.03043 · doi:10.2307/2274135
[21] Myong-Hi Kim, Topological complexity of a root finding algorithm, J. Complexity 5 (1989), no. 3, 331 – 344. · Zbl 0689.65030 · doi:10.1016/0885-064X(89)90029-0
[22] 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. · Zbl 0606.68039
[23] Michael Machtey and Paul Young, An introduction to the general theory of algorithms, North-Holland, New York-Oxford-Shannon, 1978. Computer Science Library — Theory of Computation Series. · Zbl 0376.68027
[24] Yu. I. Manin, A course in mathematical logic, Springer-Verlag, New York-Berlin, 1977. Translated from the Russian by Neal Koblitz; Graduate Texts in Mathematics, Vol. 53. · Zbl 0383.03002
[25] Zohar Manna, Mathematical theory of computation, McGraw-Hill Book Co., New York-Düsseldorf-Johannesburg, 1974. McGraw-Hill Computer Science Series. · Zbl 0353.68066
[26] Barry Mazur, Arithmetic on curves, Bull. Amer. Math. Soc. (N.S.) 14 (1986), no. 2, 207 – 259. · Zbl 0593.14021
[27] J. Milnor, On the Betti numbers of real varieties, Proc. Amer. Math. Soc. 15 (1964), 275 – 280. · Zbl 0123.38302
[28] Marvin L. Minsky, Computation: finite and infinite machines, Prentice-Hall, Inc., Englewood Cliffs, N.J., 1967. Prentice-Hall Series in Automatic Computation. · Zbl 0195.02402
[29] Marian Boykan Pour-El and Ian Richards, Computability and noncomputability in classical analysis, Trans. Amer. Math. Soc. 275 (1983), no. 2, 539 – 560. · Zbl 0513.03031
[30] Franco P. Preparata and Michael Ian Shamos, Computational geometry, Texts and Monographs in Computer Science, Springer-Verlag, New York, 1985. An introduction. · Zbl 0575.68059
[31] Michael O. Rabin, Computable algebra, general theory and theory of computable fields., Trans. Amer. Math. Soc. 95 (1960), 341 – 360. · Zbl 0156.01201
[32] Michael O. Rabin, Proving simultaneous positivity of linear forms, J. Comput. System Sci. 6 (1972), 639 – 650. Third Annual ACM Symposium on the Theory of Computing (Shaker Heights, Ohio, 1971). · Zbl 0274.68022 · doi:10.1016/S0022-0000(72)80034-5
[33] Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967.
[35] J. C. Shepherdson and H. E. Sturgis, Computability of recursive functions, J. Assoc. Comput. Mach. 10 (1963), 217 – 255. · Zbl 0118.25401 · doi:10.1145/321160.321170
[36] 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. · Zbl 0409.68030 · doi:10.1007/3-540-09510-1_42
[37] Steve Smale, On the topology of algorithms. I, J. Complexity 3 (1987), no. 2, 81 – 89. · Zbl 0639.68042 · doi:10.1016/0885-064X(87)90021-5
[38] Eduardo D. Sontag, Polynomial response maps, Lecture Notes in Control and Information Sciences, vol. 13, Springer-Verlag, Berlin-New York, 1979. · Zbl 0413.93004
[39] J. Michael Steele and Andrew C. Yao, Lower bounds for algebraic decision trees, J. Algorithms 3 (1982), no. 1, 1 – 8. · Zbl 0477.68065 · doi:10.1016/0196-6774(82)90002-5
[40] Volker Strassen, Algebraische Berechnungskomplexität, Perspectives in mathematics, Birkhäuser, Basel, 1984, pp. 509 – 550 (German). · Zbl 0572.68026
[41] Alfred Tarski, A decision method for elementary algebra and geometry, University of California Press, Berkeley and Los Angeles, Calif., 1951. 2nd ed. · Zbl 0035.00602
[42] 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). · Zbl 0137.42503
[43] 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. · Zbl 0468.68037 · doi:10.1007/3-540-11160-3_7
[44] J. F. Traub and H. Woźniakowski, Complexity of linear programming, Oper. Res. Lett. 1 (1981/82), no. 2, 59 – 62. · Zbl 0486.90060 · doi:10.1016/0167-6377(82)90047-5
[45] 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.
[46] Lou van den Dries, Alfred Tarski’s elimination theory for real closed fields, J. Symbolic Logic 53 (1988), no. 1, 7 – 19. · Zbl 0651.03001 · doi:10.2307/2274424
[47] Joachim von zur Gathen, Algebraic complexity theory, Annual review of computer science, Vol. 3, Annual Reviews, Palo Alto, CA, 1988, pp. 317 – 347.
[48] 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. · Zbl 0441.68045
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.