文章基本信息

标题：Polynomial Running Times for Polynomial-Time Oracle Machines
本地全文：下载
作者：Akitoshi Kawamura ; Florian Steinberg
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2017
卷号：84
页码：23:1-23:18
DOI：10.4230/LIPIcs.FSCD.2017.23
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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.
关键词：second-order complexity; oracle Turing machine; computable analysis; second-order polynomial; computational complexity of partial functionals