On function spaces and polynomial-time computability.
Akitoshi Kawamura, Arno Pauly · arXiv (Cornell University) · 2014
In Computable Analysis, elements of uncountable spaces, such as the real line R, are represented by functions on strings and fed to Turing machines as oracles; or equivalently, they are represented by infinite strings and written on the tapes of Turing machines [Wei00, BHW08]. To obtain reasonable notions of computability and complexity, it is hence important to choose the “right ” representation (encoding) for the spaces being considered. Let’s say we have already agreed upon representations and ı of spaces X and Y (that are admissible with the topologies of X and Y). How would we represent the space CŒX!Y � of continuous functions from X to Y? It is known that there is a natural representation Œ! ı� of CŒX! Y � which is characterized by the property that it is the poorest representation that makes function evaluation computable [Wei00, Lemma 3.3.14]. Is there a representation with a similar property also at the level of polynomial-time computability (as introduced in [KF82] and extended in [KC96, KC12])? In this note we observe that there is such a nice representation for the space of continuous real-valued functions. Generalization to other spaces is left for future research. 1. TYPE-TWO POLYNOMIAL-TIME COMPUTABILITY We consider computational problems as multi-valued functions from the set X of possible inputs to the set Y of possible outputs. An.X; Y /-problem F is formally a subset of X Y. The set of x 2 X such that there is y 2 Y with.x; y / 2 F is called the domain of definition or the promise of F and denoted dom F. For x 2 dom F, we write FŒx � for the (nonempty) set of all such y. If FŒx � is a singleton, we write F.x / for the unique element of FŒx�. When this is the case for all x 2 dom F, we say that F is a single-valued problem, or a partial function. When dom F D X, we say that F is total. A single-valued total problem is called a function. The intuitive interpretation is that F specifies a problem where, given any x 2 dom F, you are required to output some element of FŒx�. Thus, the specification becomes stricter as dom F gets bigger or as FŒx � (for some x 2 dom F) gets smaller. For a.Y; Z/-problem F and an.X; Y /-problem G, we define the.X; Z/-problem F ı G by saying that its promise is (1) dom.F ı G / D f x 2 dom G W GŒx � dom F g; and that, for any x in this promise, (2).F ı G/Œx � D [ y2GŒx�