Function spaces for second-order polynomial time

2014/01/13 by Akitoshi Kawamura, Kawamura, Akitoshi, Arno Pauly +1
Computer Science · Mathematics · #03D30 #03D65 #68Q15 #Computational Complexity (cs.CC) #F.1.3 #FOS: Computer and information sciences #FOS: Mathematics #I.1.1 #Logic (math.LO) #Logic in Computer Science (cs.LO) #acm:03D30 #acm:03D65 #acm:68Q15 #cs.CC #cs.LO #math.LO #msc:03D30 #msc:03D65 #msc:68Q15

paper · pdf · doi:10.48550/arxiv.1401.2861

arxiv created 2015/10/27 · arxiv updated 2015/10/28

Abstract

In the context of second-order polynomial-time computability, we prove that there is no general function space construction. We proceed to identify restrictions on the domain or the codomain that do provide a function space with polynomial-time function evaluation containing all polynomial-time computable functions of that type. As side results we show that a polynomial-time counterpart to admissibility of a representation is not a suitable criterion for natural representations, and that the Weihrauch degrees embed into the polynomial-time Weihrauch degrees.

Related

• Representations and evaluation strategies for feasibly approximable functions
• Comparing representations for function spaces in computable analysis
• Polynomial running times for polynomial-time oracle machines
• A syntactical analysis of non-size-increasing polynomial time computation
• Computable real function F such that F is not polynomial time computable on [0,1]