Parametrised second-order complexity theory with applications to the study of interval computation

DOI10.1016/j.tcs.2019.05.009zbMath1454.03057arXiv1711.10530OpenAlexW2771971039WikidataQ127816689 ScholiaQ127816689MaRDI QIDQ2285136

Florian Steinberg, Eike Neumann

Publication date: 16 January 2020

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

Full work available at URL: https://arxiv.org/abs/1711.10530

zbMATH Keywords

interval computationcomputable analysissecond-order complexitytype-two complexity

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Higher-type and set recursion theory (03D65) Computation over the reals, computable analysis (03D78)

Related Items (3)

Unnamed Item ⋮ Quantitative continuity and Computable Analysis in Coq ⋮ Quantitative coding and complexity theory of compact metric spaces

Uses Software

• Ariadne
• iRRAM

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Computational complexity of solving polynomial differential equations over unbounded domains
• Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• The basic feasible functionals in computable analysis
• The computational complexity of maximization and integration
• Theory of representations
• Computational complexity of real functions
• Polynomial and abstract subrecursive classes
• Extended admissibility.
• Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving
• Analytical properties of resource-bounded real functionals
• On characterizations of the basic feasible functionals, Part I
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1$$]
• Small Complexity Classes for Computable Analysis
• Complexity Theory for Operators in Analysis
• Spaces allowing Type‐2 Complexity Theory revisited
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
• Computable functionals
• On the definition of computable functionals
• On the definitions of computable real continuous functions
• On the computational complexity of ordinary differential equations
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• A new Characterization of Type-2 Feasibility
• Average-case polynomial-time computability of hamiltonian dynamics
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Bounded time computation on metric spaces and Banach spaces
• Function Spaces for Second-Order Polynomial Time
• On the Query Complexity of Real Functionals
• Computer Science Logic

This page was built for publication: Parametrised second-order complexity theory with applications to the study of interval computation