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 analysiscomputational complexity of partial functionalsoracle Turing machinesecond-order complexitysecond-order polynomial

Mathematics Subject Classification ID

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

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

• 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
• scientific article; zbMATH DE number 66471 (Why is no real title available?)
• On the Computational Complexity of Positive Linear Functionals on $$\mathcal{C}[0;1]$$
• On the query complexity of real functionals
• Polynomial and abstract subrecursive classes
• Polynomial Running Times for Polynomial-Time Oracle Machines
• 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

(8)

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

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)