Analytical properties of resource-bounded real functionals

DOI10.1016/J.JCO.2014.02.008MaRDI QIDQ2509953zbMATH OpenOpenAlexFDO

Authors Hugo Férée, Walid Gomaa, Mathieu Hoyrup

Publication date 31 July 2014

Published in Journal of Complexity (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jco.2014.02.008

zbMATH Keywords

computable analysiscomputational complexitynon-deterministic complexitynormoracle Turing machinepolynomial time computable functional

Mathematics Subject Classification ID

Turing machines and related notions (03D10) Complexity of computation (including implicit computational complexity) (03D15) Computation over the reals, computable analysis (03D78) Analysis of algorithms and problem complexity (68Q25)

Recommendations

• On the query complexity of real functionals
• Complexity theory for operators in analysis
• Complexity theory for operators in analysis
• The basic feasible functionals in computable analysis
• scientific article; zbMATH DE number 52121

Cites work

• A tutorial on computable analysis
• Complexity for type-2 relations
• Complexity theory for operators in analysis
• Complexity theory for operators in analysis
• Computable functionals
• Computational complexity of real functions
• Computational complexity on computable metric spaces
• scientific article; zbMATH DE number 3112803 (Why is no real title available?)
• scientific article; zbMATH DE number 52121 (Why is no real title available?)
• scientific article; zbMATH DE number 1022519 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• On the Kolmogorov complexity of continuous real functions
• On the Kolmogorov complexity of continuous real functions
• On the query complexity of real functionals
• Spaces allowing Type‐2 Complexity Theory revisited
• The computational complexity of maximization and integration
• The maximum value problem and NP real numbers

Cited in

(6)

• Parametrised second-order complexity theory with applications to the study of interval computation
• Game semantics approach to higher-order complexity
• Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
• Polynomial Running Times for Polynomial-Time Oracle Machines
• On the query complexity of real functionals
• Simulation of Turing machines with analytic discrete ODEs: polynomial-time and space over the reals characterised with discrete ordinary differential equations

This page was built for publication: Analytical properties of resource-bounded real functionals

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2509953)