Computational complexity of real functions
From MaRDI portal
Publication:1171056
DOI10.1016/S0304-3975(82)80003-0zbMath0498.03047OpenAlexW2006786362MaRDI QIDQ1171056
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
rootsmaximum valuepolynomial timeintegraloracle Turing machinenowhere differentiable functioncontinuity of a real functionNP theory
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
