ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS: NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES

ON A THEORY OF COMPUTATION AND COMPLEXITY OVER THE REAL NUMBERS: NP-COMPLETENESS, RECURSIVE FUNCTIONS AND UNIVERSAL MACHINES

July 1989 | LENORE BLUM, MIKE SHUB AND STEVE SMALE
This paper presents a model of computation over the real numbers or an arbitrary ordered ring R. It introduces universal machines, partial recursive functions, and NP-complete problems in this setting. The theory reflects classical computation over the integers but also incorporates the unique mathematical properties of the ring R. It provides a framework for studying foundational issues in numerical analysis and computation. The paper discusses the computational complexity of problems over the reals, including the NP-completeness of the 4-Feasibility problem, which involves determining whether a real degree 4 polynomial has a zero. It shows that while NP-problems over the integers are solvable in exponential time, those over the reals require exponential bounds due to the infinite nature of real numbers. The paper also explores the concept of R.E. sets over R, showing that they can be non-countable and include examples like basins of attraction of complex dynamical systems. The paper introduces a universal machine over R, which can simulate any machine over R. It also defines computable functions over R as partial recursive functions and discusses the algebraic structure of these functions. The paper links computational theory with dynamical systems, using examples like Julia sets to illustrate undecidable sets over the reals. Key results include the characterization of R.E. sets over R, the NP-completeness of the 4-Feasibility problem over R, and the existence of a universal machine over R. The paper also discusses the computational complexity of problems like the Travelling Salesman Problem over R and the implications of these results for the P vs NP question over the reals and integers. The paper concludes with a discussion of the broader implications of these results for computational theory and numerical analysis.This paper presents a model of computation over the real numbers or an arbitrary ordered ring R. It introduces universal machines, partial recursive functions, and NP-complete problems in this setting. The theory reflects classical computation over the integers but also incorporates the unique mathematical properties of the ring R. It provides a framework for studying foundational issues in numerical analysis and computation. The paper discusses the computational complexity of problems over the reals, including the NP-completeness of the 4-Feasibility problem, which involves determining whether a real degree 4 polynomial has a zero. It shows that while NP-problems over the integers are solvable in exponential time, those over the reals require exponential bounds due to the infinite nature of real numbers. The paper also explores the concept of R.E. sets over R, showing that they can be non-countable and include examples like basins of attraction of complex dynamical systems. The paper introduces a universal machine over R, which can simulate any machine over R. It also defines computable functions over R as partial recursive functions and discusses the algebraic structure of these functions. The paper links computational theory with dynamical systems, using examples like Julia sets to illustrate undecidable sets over the reals. Key results include the characterization of R.E. sets over R, the NP-completeness of the 4-Feasibility problem over R, and the existence of a universal machine over R. The paper also discusses the computational complexity of problems like the Travelling Salesman Problem over R and the implications of these results for the P vs NP question over the reals and integers. The paper concludes with a discussion of the broader implications of these results for computational theory and numerical analysis.
Reach us at info@study.space
Understanding On a theory of computation and complexity over the real numbers%3B np-completeness