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

DOI10.1016/J.TCS.2019.05.009MaRDI QIDQ2285136zbMATH OpenOpenAlexWikidataFDO

Authors Eike Neumann, Florian Steinberg

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, https://publications.aston.ac.uk/id/eprint/39143/1/Parametrised_second_order_complexity_theory.pdf

zbMATH Keywords

computable analysisinterval computationsecond-order complexitytype-two complexity

Mathematics Subject Classification ID

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

Abstract: We extend the framework for complexity of operators in analysis devised by Kawamura and Cook (2012) to allow for the treatment of a wider class of representations. The main novelty is to endow represented spaces of interest with an additional function on names, called a parameter, which measures the complexity of a given name. This parameter generalises the size function which is usually used in second-order complexity theory and therefore also central to the framework of Kawamura and Cook. The complexity of an algorithm is measured in terms of its running time as a second-order function in the parameter, as well as in terms of how much it increases the complexity of a given name, as measured by the parameters on the input and output side. As an application we develop a rigorous computational complexity theory for interval computation. In the framework of Kawamura and Cook the representation of real numbers based on nested interval enclosures does not yield a reasonable complexity theory. In our new framework this representation is polytime equivalent to the usual Cauchy representation based on dyadic rational approximation. By contrast, the representation of continuous real functions based on interval enclosures is strictly smaller in the polytime reducibility lattice than the usual representation, which encodes a modulus of continuity. Furthermore, the function space representation based on interval enclosures is optimal in the sense that it contains the minimal amount of information amongst those representations which render evaluation polytime computable.

Recommendations

• Complexity theory for spaces of integrable functions
• Representations and evaluation strategies for feasibly approximable functions
• Closed sets and operators thereon: representations, computability and complexity
• Complexity theory for operators in analysis
• Computer Science Logic

Cites work

• 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 65741 (Why is no real title available?)
• scientific article; zbMATH DE number 1223632 (Why is no real title available?)
• scientific article; zbMATH DE number 1969324 (Why is no real title available?)
• scientific article; zbMATH DE number 1460545 (Why is no real title available?)
• scientific article; zbMATH DE number 1746043 (Why is no real title available?)
• A new Characterization of Type-2 Feasibility
• Analytical properties of resource-bounded real functionals
• Average-case polynomial-time computability of Hamiltonian dynamics
• Bounded time computation on metric spaces and Banach spaces
• COMPLEXITY AND REAL COMPUTATION: A MANIFESTO
• Complexity theory for operators in analysis
• Complexity theory for spaces of integrable functions
• Computable functionals
• Computational benefit of smoothness: parameterized bit-complexity of numerical operators on analytic functions and Gevrey's hierarchy
• Computational complexity of real functions
• Computational complexity of solving polynomial differential equations over unbounded domains
• Computer Science Logic
• Extended admissibility.
• Function spaces for second-order polynomial time
• Lipschitz continuous ordinary differential equations are polynomial-space complete
• On a theory of computation and complexity over the real numbers: 𝑁𝑃- completeness, recursive functions and universal machines
• On characterizations of the basic feasible functionals. I
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• On the computational complexity of ordinary differential equations
• On the definition of computable functionals
• On the definitions of computable real continuous functions
• On the query complexity of real functionals
• Parameterized complexity for uniform operators on multidimensional analytic functions and ODE solving
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Polynomial and abstract subrecursive classes
• Small complexity classes for computable analysis
• Spaces allowing Type‐2 Complexity Theory revisited
• The basic feasible functionals in computable analysis
• The computational complexity of maximization and integration
• Theory of representations
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis

Cited in

(5)

• A Shift-free Characterization of NP within Interval-valued Computing
• Computable analysis and notions of continuity in \textsc{Coq}
• On the complexity of robust eventual inequality testing for C-finite functions
• Quantitative continuity and Computable Analysis in Coq
• Quantitative coding and complexity theory of compact metric spaces

Describes a project that uses

Uses Software

• iRRAM
• Ariadne

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

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