# Analogue of the topology-computability correspondence for computational complexity

There is an interesting correspondence between notions of topology and notions of computability theory originating from the ingenious idea of Dana Scott to identify computable functions with continuous functions (in fact it can perhaps be traced back to Brouwer).

Complexity theory can be seen as a refinement of computability theory: we are interested in not only whether a problem is solvable or not but also the efficiency with which it is solvable. Taking this view of complexity theory as a refinement of computability theory, I wonder if there is any research on analogous mathematical structures to provide efficiency-sensitive denotational semantics to programming languages.

The point of topology is that it is distance-blind which is in accord with the efficiency-blind approach in computability theory. So it seems to me that an efficiency-sensitive denotational structure should be a topological space with a notion of distance, i.e., a metric space or something like that.

Has someone worked this out or is this a nonsensical question? If it is the latter, please explain why.

• Where did Dana Scott identify computable and continuous functions? To the best of my knowledge, he's always explained that continuity is a good substitute for computability, in the sense that every computable map is continuous, and that many arguments in computability rely on this fact. Jun 30 '20 at 19:34
• Also note that the kind of topology that is relevant to computability theory is almost never metrizable (not even $T_1$) so your intuition that this has somethiing to do with distance or "distance-blindness" is perhaps leading you astray. Jun 30 '20 at 19:35