Polynomial Running Times for Polynomial-Time Oracle Machines

DOI10.4230/LIPICS.FSCD.2017.23zbMATH Open1434.03117arXiv1704.01405OpenAlexW2606501292MaRDI QIDQ5111319FDOQ5111319

Florian Steinberg, Akitoshi Kawamura

Publication date: 26 May 2020

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.

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

Recommendations

• Type-two polynomial-time and restricted lookahead
• Type-two polynomial-time and restricted lookahead
• A new Characterization of Type-2 Feasibility
• Some applications of logic to feasibility in higher types

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)

Cites Work

• Analytical properties of resource-bounded real functionals
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
• Function Spaces for Second-Order Polynomial Time
• Title not available (Why is that?)
• Polynomial and abstract subrecursive classes
• A new Characterization of Type-2 Feasibility
• Complexity Theory of (Functions on) Compact Metric Spaces
• The basic feasible functionals in computable analysis
• Polynomial Running Times for Polynomial-Time Oracle Machines
• On the Query Complexity of Real Functionals
• Small Complexity Classes for Computable Analysis
• Complexity Theory for Operators in Analysis
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• Bounded time computation on metric spaces and Banach spaces

Cited In (7)

• Type-two polynomial-time and restricted lookahead
• 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}\)
• Polynomial Running Times for Polynomial-Time Oracle Machines
• Complete and tractable machine-independent characterizations of second-order polytime
• Title not available (Why is that?)
• 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)