Polynomial Running Times for Polynomial-Time Oracle Machines

DOI10.4230/LIPIcs.FSCD.2017.23zbMath1434.03117arXiv1704.01405OpenAlexW2606501292MaRDI QIDQ5111319

Florian Steinberg, Akitoshi Kawamura

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) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Computation over the reals, computable analysis (03D78)

Related Items (6)

Complete and tractable machine-independent characterizations of second-order polytime ⋮ Type-two polynomial-time and restricted lookahead ⋮ Unnamed Item ⋮ Parametrised second-order complexity theory with applications to the study of interval computation ⋮ Polynomial Running Times for Polynomial-Time Oracle Machines ⋮ Quantitative coding and complexity theory of compact metric spaces

Cites Work

• Unnamed Item
• The basic feasible functionals in computable analysis
• Polynomial and abstract subrecursive classes
• Analytical properties of resource-bounded real functionals
• 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
• Towards Computational Complexity Theory on Advanced Function Spaces in Analysis
• Complexity Theory of (Functions on) Compact Metric Spaces
• A new Characterization of Type-2 Feasibility
• 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

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