Polynomial Running Times for Polynomial-Time Oracle Machines

DOI10.4230/LIPICS.FSCD.2017.23MaRDI QIDQ5111319zbMATH OpenOpenAlexFDO

Authors Akitoshi Kawamura, Florian Steinberg

Publication date 26 May 2020

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

zbMATH Keywords

computable analysisoracle Turing machinesecond-order complexitysecond-order polynomialcomputational complexity of partial functionals

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computation over the reals, computable analysis (03D78) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Abstract: This paper introduces a more restrictive notion of feasibility of functionals on Baire space than the established one from second-order complexity theory. Thereby making it possible to consider functions on the natural numbers as running times of oracle Turing machines and avoiding second-order polynomials, which are notoriously difficult to handle. Furthermore, all machines that witness this stronger kind of feasibility can be clocked and the different traditions of treating partial operators from computable analysis and second-order complexity theory are equated in a precise sense. The new notion is named "strong polynomial-time computability", and proven to be a strictly stronger requirement than polynomial-time computability. It is proven that within the framework for complexity of operators from analysis introduced by Kawamura and Cook the classes of strongly polynomial-time computable operators and polynomial-time computable operators coincide.

Recommendations

• A new Characterization of Type-2 Feasibility
• Some applications of logic to feasibility in higher types

Cites work

• scientific article; zbMATH DE number 66471 (Why is no real title available?)
• A new Characterization of Type-2 Feasibility
• Analytical properties of resource-bounded real functionals
• Bounded time computation on metric spaces and Banach spaces
• Complexity theory for operators in analysis
• Complexity theory of (functions on) compact metric spaces
• Function spaces for second-order polynomial time
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• On the query complexity of real functionals
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Polynomial and abstract subrecursive classes
• Small complexity classes for computable analysis
• The basic feasible functionals in computable analysis
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis

Cited in

(7)

• Function spaces for second-order polynomial time
• Parametrised second-order complexity theory with applications to the study of interval computation
• The polynomial-time hierarchy and oracle set \(A \in \text{PH/poly}\)
• A tier-based typed programming language characterizing feasible functionals
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Complete and tractable machine-independent characterizations of second-order polytime
• Quantitative coding and complexity theory of compact metric spaces

This page was built for publication: Polynomial Running Times for Polynomial-Time Oracle Machines

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