Polynomial Running Times for Polynomial-Time Oracle Machines

Kawamura, Akitoshi; Steinberg, Florian

doi:10.4230/LIPIcs.FSCD.2017.23

File

LIPIcs.FSCD.2017.23.pdf

Filesize: 0.58 MB
18 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FSCD.2017.23
URN: urn:nbn:de:0030-drops-77370

Author Details

Akitoshi Kawamura

Florian Steinberg

Cite AsGet BibTex

Akitoshi Kawamura and Florian Steinberg. Polynomial Running Times for Polynomial-Time Oracle Machines. In 2nd International Conference on Formal Structures for Computation and Deduction (FSCD 2017). Leibniz International Proceedings in Informatics (LIPIcs), Volume 84, pp. 23:1-23:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2017)
https://doi.org/10.4230/LIPIcs.FSCD.2017.23

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 functionals 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 functionals and polynomial-time computable functionals coincide.

Keywords

second-order complexity
oracle Turing machine
computable analysis
second-order polynomial
computational complexity of partial functionals

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

References

Franz Brauße and Florian Steinberg. A minimal representation for continuous functions. https://arxiv.org/abs/1703.10044, 2017. Preprint.
Stephen A. Cook. Computational complexity of higher type functions. In Proceedings of the International Congress of Mathematicians, Vol. I, II (Kyoto, 1990), pages 55-69. Math. Soc. Japan, Tokyo, 1991.
Hugo Férée, Walid Gomaa, and Mathieu Hoyrup. Analytical properties of resource-bounded real functionals. J. Complexity, 30(5):647-671, 2014. URL: http://dx.doi.org/10.1016/j.jco.2014.02.008.
Hugo Férée and Mathieu Hoyrup. Higher order complexity in analysis, 2013. CCA. URL: https://hal.inria.fr/hal-00915973/document.
Hugo Férée and Martin Ziegler. On the computational complexity of positive linear functionals on c[0;1], 2015. MACIS conference. URL: https://hugo.feree.fr/macis2015.pdf.
B. M. Kapron and S. A. Cook. A new characterization of type-2 feasibility. SIAM J. Comput., 25(1):117-132, 1996. URL: http://dx.doi.org/10.1137/S0097539794263452.
Akitoshi Kawamura. Computational Complexity in Analysis and Geometry. PhD thesis, University of Toronto, 2011.
Akitoshi Kawamura and Stephen Cook. Complexity theory for operators in analysis. ACM Trans. Comput. Theory, 4(2):5:1-5:24, May 2012. URL: http://dx.doi.org/10.1145/2189778.2189780.
Akitoshi Kawamura and Hiroyuki Ota. Small complexity classes for computable analysis. In Mathematical foundations of computer science 2014. Part II, volume 8635 of Lecture Notes in Comput. Sci., pages 432-444. Springer, Heidelberg, 2014. URL: http://dx.doi.org/10.1007/978-3-662-44465-8_37.
Akitoshi Kawamura and Arno Pauly. Function spaces for second-order polynomial time. In Language, life, limits, volume 8493 of Lecture Notes in Comput. Sci., pages 245-254. Springer, Cham, 2014. URL: http://dx.doi.org/10.1007/978-3-319-08019-2_25.
Akitoshi Kawamura, Florian Steinberg, and Martin Ziegler. Complexity theory of (functions on) compact metric spaces. In Proceedings of the 31st Annual ACM/IEEE Symposium on Logic in Computer Science, LICS'16, pages 837-846, New York, NY, USA, 2016. ACM. URL: http://dx.doi.org/10.1145/2933575.2935311.
Akitoshi Kawamura, Florian Steinberg, and Martin Ziegler. Towards computational complexity theory on advanced function spaces in analysis. In Arnold Beckmann, Laurent Bienvenu, and Nataša Jonoska, editors, Pursuit of the Universal: 12th Conference on Computability in Europe, CiE 2016, Paris, France, June 27 - July 1, 2016, Proceedings, pages 142-152. Springer, Cham, 2016. URL: http://dx.doi.org/10.1007/978-3-319-40189-8_15.
Aktioshi Kawamura and Florian Steinberg. Polynomial running times for polynomial-time oracle machines. https://arxiv.org/abs/1704.01405, 2017. Preprint.
Branimir Lambov. The basic feasible functionals in computable analysis. J. Complexity, 22(6):909-917, 2006. URL: http://dx.doi.org/10.1016/j.jco.2006.06.005.
Kurt Mehlhorn. Polynomial and abstract subrecursive classes. J. Comput. System Sci., 12(2):147-178, 1976. Sixth Annual ACM Symposium on the Theory of Computing (Seattle, Wash., 1974).
Matthias Schröder and Florian Steinberg. Bounded time computation on metric spaces and Banach spaces. https://arxiv.org/abs/1701.02274, 2017. Preprint; extended abstract accepted for LICS 2017 conference.