Computational complexity of real functions

DOI10.1016/S0304-3975(82)80003-0zbMath0498.03047OpenAlexW2006786362MaRDI QIDQ1171056

Ker-I. Ko, Harvey M. Friedman

Publication date: 1982

Published in: Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0304-3975(82)80003-0

zbMATH Keywords

rootsmaximum valuepolynomial timeintegraloracle Turing machinenowhere differentiable functioncontinuity of a real functionNP theory

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Constructive and recursive analysis (03F60) Complexity of computation (including implicit computational complexity) (03D15)

Related Items (78)

The Hausdorff-Ershov hierarchy in Euclidean spaces ⋮ Characterizing time computational complexity classes with polynomial differential equations ⋮ Continuous optimization problems and a polynomial hierarchy of real functions ⋮ Approximation to measurable functions and its relation to probabilistic computation ⋮ The complexity of generating test instances ⋮ On the continued fraction representation of computable real numbers ⋮ Recursive characterization of computable real-valued functions and relations ⋮ Some properties of sets tractable under every polynomial-time computable distribution ⋮ Computing power series in polynomial time ⋮ Computability of probability measures and Martin-Löf randomness over metric spaces ⋮ On the complexity of finding circumscribed rectangles and squares for a two-dimensional domain ⋮ On the complexity of computing the logarithm and square root functions on a complex domain ⋮ Recursively enumerable subsets of \(\mathbb{R}^{q}\) in two computing models Blum-Shub-Smale machine and Turing machine ⋮ On parallel complexity of analytic functions ⋮ A graph-theoretical basis of stochastic-cascading network influence: characterizations of influence-based centrality ⋮ On the complexity of algebraic numbers, and the bit-complexity of straight-line programs1 ⋮ On the computational complexity of the Dirichlet Problem for Poisson's Equation ⋮ Sets computable in polynomial time on average ⋮ On the complexity of computable real sequences ⋮ COMPUTABLY COMPACT METRIC SPACES ⋮ Hierarchies of function classes defined by the first-value operator ⋮ On the complexity of computing the Hausdorff distance ⋮ Exponential lower bounds for finding Brouwer fixed points ⋮ The maximum value problem and NP real numbers ⋮ Computable preference and utility ⋮ On continuous one-way functions ⋮ QUANTUM COMPUTATION WITH RESTRICTED AMPLITUDES ⋮ In Memoriam: Ker-I Ko (1950–2018) ⋮ Solovay reducibility and continuity ⋮ On the time complexity of partial real functions ⋮ Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy ⋮ Average-case polynomial-time computability of hamiltonian dynamics ⋮ On the complexity of online computations of real functions ⋮ A polynomial-time computable curve whose interior has a nonrecursive measure ⋮ On the definitions of some complexity classes of real numbers ⋮ Trivial Reals ⋮ Fixed Points on the Real Numbers without the Equality Test ⋮ Complexity of Operators on Compact Sets ⋮ On the computational complexity of integral equations ⋮ Curves that must be retraced ⋮ Uniformity of quantum circuit families for error-free algorithms ⋮ Type 2 computational complexity of functions on Cantor's space ⋮ Analytical properties of resource-bounded real functionals ⋮ Computable metrics above the standard real metric ⋮ Parametrised second-order complexity theory with applications to the study of interval computation ⋮ On subrecursive complexity of integration ⋮ Computability on computable metric spaces ⋮ Perfect computational equivalence between quantum Turing machines and finitely generated uniform quantum circuit families ⋮ Complexity of the calculus of continued fraction representation of real numbers ⋮ Multi-Resolution Cellular Automata for Real Computation ⋮ FOUNDATIONS OF ONLINE STRUCTURE THEORY ⋮ Relatively recursive reals and real functions ⋮ On the computational complexity of best Chebyshev approximations ⋮ On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines ⋮ Grzegorczyk's hierarchy of computable analysis ⋮ Representations and evaluation strategies for feasibly approximable functions ⋮ Computability on subsets of Euclidean space. I: Closed and compact subsets ⋮ On approximate and algebraic computability over the real numbers ⋮ Computability structure of the Sobolev spaces and its applications ⋮ Polynomial time samplable distributions ⋮ Unnamed Item ⋮ Rational presented metric spaces and complexity, the case of the space of real functions uniformly continuous on a compact interval ⋮ Reducibilities on real numbers ⋮ The computational complexity of maximization and integration ⋮ A SCHEMATIC DEFINITION OF QUANTUM POLYNOMIAL TIME COMPUTABILITY ⋮ European Summer Meeting of the Association for Symbolic Logic ⋮ Computational complexity of classical solutions of partial differential equations ⋮ On the complexity of conversion between classic real number representations ⋮ Computational complexity of uniform quantum circuit families and quantum Turing machines ⋮ Real functions, contraction mappings, and P-completeness ⋮ Uniform computational complexity of the derivatives of \(C^{\infty}\)-functions. ⋮ Effectively closed sets and graphs of computable real functions. ⋮ Effective metric spaces and representations of the reals. ⋮ Real functions computable by finite automata using affine representations. ⋮ Presentations of computably enumerable reals. ⋮ Normality in non-integer bases and polynomial time randomness ⋮ Étude constructive de problèmes de topologie pour les réels irrationnels ⋮ Theory of representations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• The maximum value problem and NP real numbers
• On computable sequences
• On the definitions of computable real continuous functions
• An Exact Method for Finding the Roots of a Complex Polynomial
• A Global Bisection Algorithm for Computing the Zeros of Polynomials in the Complex Plane
• A Machine-Independent Theory of the Complexity of Recursive Functions
• Analysis in the Computable Number Field
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Nicht konstruktiv beweisbare Sätze der Analysis
• Criteria of constructibility for real numbers
• Recursive Real Numbers

This page was built for publication: Computational complexity of real functions