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

DOI10.1090/S0273-0979-1989-15750-9zbMath0681.03020OpenAlexW2071846104WikidataQ60781615 ScholiaQ60781615MaRDI QIDQ4729768

Michael Shub, Lenore Blum, Stephen Smale

Publication date: 1989

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1090/s0273-0979-1989-15750-9

zbMATH Keywords

NP-completeness recursive function computation theory universal machine computation over the reals 4-feasibility problem complements of Julia sets computation over an ordered ring undecidable sets

Mathematics Subject Classification ID

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

Related Items

A seven-dimensional family of simple harmonic functions, Derandomization and absolute reconstruction for sums of powers of linear forms, Analog computation via neural networks, Deciding probabilistic automata weak bisimulation: theory and practice, Computability with low-dimensional dynamical systems, Complexity and dimension, Formulation of linear problems and solution by a universal machine, Separation of complexity classes in Koiran's weak model, Relativizations of the P=?NP question over the reals (and other ordered rings), Deviation theorems for solutions of differential equations and applications to lower bounds on parallel complexity of sigmoids, On Kolmogorov complexity in the real Turing machine setting, On the computing power of fuzzy Turing machines, Simulation of simultaneous safe recursion over an arbitrary structure, Hardy is (almost) everywhere: nonlocality without inequalities for almost all entangled multipartite states, On rational functions of first-class complexity, Discrete Morse theory for computing cellular sheaf cohomology, Bounding the equivariant Betti numbers of symmetric semi-algebraic sets, Approximating shortest path for the skew lines problem in time doubly logarithmic in 1/epsilon, On invariance of degree for certain computations, Computability of a map and decidability of its graph in the model of Blum, Shub and Smale, Recursively enumerable subsets of \(\mathbb{R}^{q}\) in two computing models Blum-Shub-Smale machine and Turing machine, Dynamical recognizers: real-time language recognition by analog computers, Universal resolution for NP-complete problems, On the complexity of \(p\)-adic basic semi-algebraic sets, On the weak computability of a four dimensional orthogonal packing and time scheduling problem, Fast linear homotopy to find approximate zeros of polynomial systems, Condition number based complexity estimate for solving polynomial systems, Optimizing \(n\)-variate \((n+k)\)-nomials for small \(k\), Effectiveness in RPL, with applications to continuous logic, A counterexample to the Hirsch conjecture, Interpolation in Valiant's theory, A complex analogue of Toda's theorem, Quantum inductive inference by finite automata, Complexity of functions: Some questions, conjectures, and results, The Turing degrees for some computation model with the real parameter, Undecidability and incompleteness in classical mechanics, Analog computation through high-dimensional physical chaotic neuro-dynamics, On a problem posed by Steve Smale, The parallel complexity of function approximation, A derivative for complex Lipschitz maps with generalised Cauchy-Riemann equations, Computing the homology of real projective sets, The complexity of optimizing over a simplex, hypercube or sphere: a short survey, On the computational complexity and geometry of the first-order theory of the reals. I: Introduction. Preliminaries. The geometry of semi-algebraic sets. The decision problem for the existential theory of the reals, Parallel information-based complexity, Statistical complexity of dominant eigenvector calculation, A size-depth trade-off for the analog computation of Boolean functions, Turing computability with neural nets, A weak version of the Blum, Shub, and Smale model, Neural networks with quadratic VC dimension, On the computation of Boolean functions by analog circuits of bounded fan-in, Fixed points, Nash equilibria, and the existential theory of the reals, Some computational problems in linear algebra as hard as matrix multiplication, Polynomial algorithms for LP over a subring of the algebraic integers with applications to LP with circulant matrices, \(P_ \mathbb{R}{}\neq{}NC_ \mathbb{R}\), A problem that is easier to solve on the unit-cost algebraic RAM, A note on a \(P \neq NP\) result for a restricted class of real machines, Two \(P\)-complete problems in the theory of the reals, Representation theorems for analytic machines and computability of analytic functions, Relations between roots and coefficients, interpolation and application to system solving, Combinatorics for computing relativistic several complex variable domains, On the ultimate complexity of factorials, A characterization of computable analysis on unbounded domains using differential equations, Computability on reals, infinite limits and differential equations, The complexity of tensor rank, Real computational universality: the word problem for a class of groups with infinite presentation, Abstract geometrical computation. III: Black holes for classical and analog computing, A hierarchy below the halting problem for additive machines, From a zoo to a zoology: Towards a general theory of graph polynomials, A refined model of computation for continuous problems, Information-based complexity: New questions for mathematicians, Exotic quantifiers, complexity classes, and complete problems, On the parallel complexity of the polynomial ideal membership problem, \(\delta\)-uniform BSS machines, Partial fraction decomposition in \(\mathbb{C}(z)\) and simultaneous Newton iteration for factorization in \(\mathbb{C}^{[z}\)], Achilles and the tortoise climbing up the hyper-arithmetical hierarchy, A domain-theoretic approach to computability on the real line, Feasible real random access machines, VPSPACE and a transfer theorem over the complex field, What is a universal computing machine?, Physically-relativized Church-Turing hypotheses: physical foundations of computing and complexity theory of computational physics, Equality is a jump, Computability on subsets of Euclidean space. I: Closed and compact subsets, Index sets in computable analysis, Analytic machines, On approximate and algebraic computability over the real numbers, On the cost of uniform and nonuniform algorithms, Concrete models of computation for topological algebras, Computation by `While' programs on topological partial algebras, Why does information-based complexity use the real number model?, Computability structure of the Sobolev spaces and its applications, On the computability of fractal dimensions and Hausdorff measure, Point-free topological spaces, functions and recursive points; filter foundation for recursive analysis. I, Complexity of computing the local dimension of a semialgebraic set, Saturation and stability in the theory of computation over the reals, Problems of combinatorial optimization, statistical sums, and representations of the full linear group, Cellular automata and discrete neural networks, Abstract geometrical computation. VII: Geometrical accumulations and computably enumerable real numbers, Mysteries of mathematics and computation, Computation of equilibria in noncooperative games, Three concepts of decidability for general subsets of uncountable spaces, Topological complexity of zero finding with algebraic operations, An analog characterization of the Grzegorczyk hierarchy, Learning from rounded-off data., Products of positive forms, linear matrix inequalities, and Hilbert 17th problem for ternary forms, Side-constrained minimum sum-of-squares clustering: mathematical programming and random projections, Computing over the reals with addition and order, On generalized Newton algorithms: Quadratic convergence, path-following and error analysis, On the complexity of quadratic programming in real number models of computation, P\(\neq\)NP over the nonstandard reals implies P\(\neq\)NP over \(\mathbb{R}\), A convex geometric approach to counting the roots of a polynomial system, Complexity of Bezout's theorem. V: Polynomial time, On the P-NP problem over real matrix rings, Polynomial algorithms for linear programming over the algebraic numbers, Toward a generalized computability theory, On the computational power of dynamical systems and hybrid systems, The simple dynamics of super Turing theories, On the relations between distributive computability and the BSS model, Recursion theory on the reals and continuous-time computation, Recursive characterization of computable real-valued functions and relations, PCF extended with real numbers, Generalized Knapsack problems and fixed degree separations, The complexity of resource allocation and price mechanisms under bounded rationality, The polynomial topological complexity of Fatou-Julia sets, Elimination of constants from machines over algebraically closed fields, Semi-algebraic complexity -- Additive complexity of matrix computational tasks, Lower bounds for arithmetic networks. II: Sum of Betti numbers, Computational complexity over the \(p\)-adic numbers, On NP-completeness for linear machines, Real data-integer solution problems within the Blum-Shub-Smale computational model, Strong spatial mixing for repulsive point processes, On the intractability of Hilbert's Nullstellensatz and an algebraic version of ``\(NP\neq P\)?, Semi-algebraic decision complexity, the real spectrum, and degree, On the complexity of solving feasible systems of linear inequalities specified with approximate data, Abstract geometrical computation. VIII: Small machines, accumulations \& rationality, Metafinite model theory, Linear programming, complexity theory and elementary functional analysis, Algorithms, complexity and discreteness criteria in \(PSL(2,C)\), A topological view on algebraic computation models, A deterministic algorithm to compute approximate roots of polynomial systems in polynomial average time, Queries with arithmetical constraints, Limiting semantics of numerical programs, Harmonic properties of the logarithmic potential and the computability of elliptic Fekete points, \(\mu\)-recursion and infinite limits., Semidefinite programming and matrix scaling over the semidefinite cone., Robust certified numerical homotopy tracking, Limits of theory sequences over algebraically closed fields and applications., Polynomial hierarchy, Betti numbers, and a real analogue of Toda's theorem, Computing exact solutions of consensus halving and the Borsuk-Ulam theorem, Natural computation and non-Turing models of computation, Continuous-time computation with restricted integration capabilities, Hypercomputation by definition, Approximate zeros and condition numbers, The real dimension problem is \(\text{NP}_{\mathbb R}\)-complete., The complexity of local dimensions for constructible sets, A note on non-complete problems in \(NP_\mathbb{R}\), Complexity of linear problems with a fixed output basis, Cook's versus Valiant's hypothesis, Abstract geometrical computation. 11: Slanted firing squad synchronisation on signal machines, Grid methods in computational real algebraic (and semialgebraic) geometry, Abstract geometrical computation. V: Embedding computable analysis, On solving univariate sparse polynomials in logarithmic time, A universal oracle for signal machines, On measures of space over real and complex numbers, An optical model of computation, On sparseness, reducibilities, and complexity, Efficient exact computation of iterated maps, Characterizations of ITBM-computability. I, On the equivariant Betti numbers of symmetric definable sets: vanishing, bounds and algorithms, Periodic generalized automata over the reals, QPLIB: a library of quadratic programming instances, Parametrised second-order complexity theory with applications to the study of interval computation, On the complexity of fitted toral dynamics, Computing the homology of semialgebraic sets. I: Lax formulas, Lower bounds for arithmetic networks, A promenade through correct test sequences. I: Degree of constructible sets, Bézout's inequality and density, The calculi of emergence: Computation, dynamics and induction, Quantum automata and quantum grammars, Interactive proofs and a Shamir-like result for real number computations, Counting problems over the reals, Isomorphism theorem for BSS recursively enumerable sets over real closed fields, The Turing closure of an Archimedean field, Efficient \(p\)-adic cell decompositions for univariate polynomials, Mathematical problems for the next century, Cake cutting: explicit examples for impossibility results, Analog computation with dynamical systems, Some aspects of studying an optimization or decision problem in different computational models, A \(\tau \)-conjecture for Newton polygons, Integration in Real PCF, A theory of complexity for continuous time systems, Real computations with fake numbers, Transfer theorems via sign conditions, Lower bounds for some decision problems over \(C\), On the computational structure of the connected components of a hard problem, Uniform computational complexity of the derivatives of \(C^{\infty}\)-functions., Effectively closed sets and graphs of computable real functions., An alternative to Ben-Or's lower bound for the knapsack problem complexity, P\(\neq\) NC over the \(p\)-adic numbers, Computational complexity of multi-player evolutionarily stable strategies, Real \(\tau \)-conjecture for sum-of-squares: a unified approach to lower bound and derandomization, Some thoughts on computational models: from massive human computing to abstract state machines, and beyond, Constructibility of the universal wave function, 1998 European Summer Meeting of the Association for Symbolic Logic, Coupled map lattices as computational systems, Overview of coupled map lattices, The Legacy of Turing in Numerical Analysis, INFLATING BALLS IS NP-HARD, Stabilité polynômiale des corps différentiels, Fast online multiplication of real numbers, Polynomial differential equations compute all real computable functions on computable compact intervals, SAFE RECURSIVE SET FUNCTIONS, Turing meets Schanuel, Logic minimization techniques with applications to cryptology, Computability and Dynamical Systems, On maps which preserve semipositivity and quantifier elimination theory for real numbers, Exact Discretization of 3-Speed Rational Signal Machines into Cellular Automata, Some basic information on information-based complexity theory, Perspectives on information-based complexity, On the expressiveness and decidability of o-minimal hybrid systems, \(\mathbf P =\mathbf{NP}\) for some structures over the binary words, Axiomatizing Analog Algorithms, Smoothing the Gap Between NP and ER, An algebraic proof of the real number PCP theorem, On the complexity of Anosov saddle transitions, Qualification Conditions in Semialgebraic Programming, Matrices of Bounded Psd Rank are Easy to Detect, A computation model with automatic functions and relations as primitive operations, Theory of computation over stream algebras, and its applications, On NC-real complexity classes for additive circuits and their relations with NC, Computation over algebraic structures and a classification of undecidable problems, Discrete Transfinite Computation, Quantifier elimination theory and maps which preserve semipositivity, Lower complexity bounds for interpolation algorithms, Vapnik-Chervonenkis Dimension of Parallel Arithmetic Computations, Rescaling Algorithms for Linear Conic Feasibility, Execution trace sets for real computation, Borel-Piecewise Continuous Reducibility for Uniformization Problems, The cost of computing integers, Average-Price and Reachability-Price Games on Hybrid Automata with Strong Resets, On the computational power of probabilistic and faulty neural networks, Efficient algorithms for computing the Euler-Poincaré characteristic of symmetric semi-algebraic sets, Fractal geometry, Turing machines and divide-and-conquer recurrences, Algorithms: From Al-Khwarizmi to Turing and Beyond, Theses for Computation and Recursion on Concrete and Abstract Structures, 2000 European Summer Meeting of the Association for Symbolic Logic. Logic Colloquium 2000, A note on parallel and alternating time, Colourful linear programming, Physical Computational Complexity and First-order Logic, Recognizing Visibility Graphs of Triangulated Irregular Networks, Recursive Quantum Functions, Avoidable Points, & Shadow Points in Recursive Analysis, On sparseness and Turing reducibility over the reals, Safe Recursion Over an Arbitrary Structure: PAR, PH and DPH, An explicit solution to Post's problem over the reals, Characterizing Computable Analysis with Differential Equations, On Relativizations of the P =? NP Question for Several Structures, Kolmogorov Complexity Theory over the Reals, Computability of Analytic Functions with Analytic Machines, Interval-valued computations and their connection with PSPACE, Turing Machines Can Be Efficiently Simulated by the General Purpose Analog Computer, SOME INITIAL THOUGHTS ON BOUNDED QUERY COMPUTATIONS OVER THE REALS, Counting complexity classes for numeric computations. II: Algebraic and semialgebraic sets, A THEORY OF COMPLEXITY, CONDITION, AND ROUNDOFF, Solving linear programs with finite precision. II: Algorithms, The many forms of hypercomputation, Computational power of infinite quantum parallelism, Unnamed Item, Algorithmic Procedures, Unnamed Item, Ordered Rings Over Which Output Sets are Recursively Enumerable Sets, Smale’s 17th problem: Average polynomial time to compute affine and projective solutions, A discreteness algorithm for 4-punctured sphere groups, Feferman on Computability, Computability, noncomputability and undecidability of maximal intervals of IVPs, Structure and Optimisation in Computational Harmonic Analysis: On Key Aspects in Sparse Regularisation, Primitive recursion in the abstract, Rigid continuation paths I. Quasilinear average complexity for solving polynomial systems, Almost Transparent Short Proofs for NPℝ, On the Kolmogorov Complexity of Continuous Real Functions, On digital nondeterminism, Undecidability in Rⁿ: Riddled Basins, the KAM Tori, and the Stability of the Solar System, On the Computational Complexity of Minimum-Concave-Cost Flow in a Two-Dimensional Grid, Decision Problems for Finite Automata over Infinite Algebraic Structures, Nonlinear phenomena in spaces of algorithms, Parts of quantum states, Rethinking arithmetic for deep neural networks, An Exact Correspondence of Linear Problems and Randomizing Linear Algorithms, Computational Power of Quantum Machines, Quantum Grammars and Feasible Computation, Quantum Computation over Continuous Variables, A complexity theory of constructible functions and sheaves, Exact real arithmetic using centred intervals and bounded error terms, Elementarily computable functions over the real numbers and \(\mathbb R\)-sub-recursive functions, Finiteness results for abelian tree models, Exact Image Reconstruction from a Single Projection through Real Computation, Iterative universal rigidity, A Survey on Analog Models of Computation, Convex generalized flows, M. Levin’s construction of absolutely normal numbers with very low discrepancy, Generalized finite automata over real and complex numbers, The PCP theorem for NP over the reals, Logics which capture complexity classes over the reals, Closure properties for fuzzy recursively enumerable languages and fuzzy recursive languages, Computability Models: Algebraic, Topological and Geometric Algorithms, Discovering the Roots: Uniform Closure Results for Algebraic Classes Under Factoring, Computational unsolvability of domains of attraction of nonlinear systems, Algebraic compressed sensing, The foundations of spectral computations via the solvability complexity index hierarchy, The Complexity of Positive Semidefinite Matrix Factorization, Analytical complexity and signal coding, The complexity of the Hausdorff distance, Complexity of optimizing over the integers, Ordered Subrings of the Reals in which Output Sets are Recursively Enumerable, Absolute reconstruction for sums of powers of linear forms: degree 3 and beyond, Trilateration using unlabeled path or loop lengths, Quantitative continuity and Computable Analysis in Coq, Metafinite model theory, Effective optimization with weighted automata on decomposable trees, Iteration, inequalities, and differentiability in analog computers, Decomposition plans for geometric constraint systems. I: Performance measures for CAD, Sparse NP-complete problems over the reals with addition, Weak arithmetics, Weak arithmetic, On weak and weighted computations over the real closure of \(\mathbb{Q}\), The stability of saturated linear dynamical systems is undecidable, The P-DNP problem for infinite Abelian groups, A polynomial-time algorithm for checking equivalence under certain semiring congruences motivated by the state-space isomorphism problem for hybrid systems, Calculs sur les structures de langage dénombrable, Learning algebraic structures from text, Complexity aspects of a semi-infinite optimization problem†, Adaptive greedy approximations, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Tractability frontiers in probabilistic team semantics and existential second-order logic over the reals, Approximating the existential theory of the reals, On the computational complexity of decision problems about multi-player Nash equilibria

Cites Work