9
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jun 30 at 19:34
  • $\begingroup$ 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. $\endgroup$ – Andrej Bauer Jun 30 at 19:35
2
$\begingroup$

The answer to your literal question is neither. The reasoning in your question makes perfect sense, and there are several researchers working on the details on what exactly is analogous to complexity theory in the same way topology is analagous to computability. However, I don't think I am unfair in claiming that this is nowhere near completed.

In a compact metric context, notions such as metric entropy seem to be important, and the counterpart to "continuous" seems to be "having a modulus of continuity of particular growth". Beyond compact metric, the picture quickly gets very unclear.

I don't know of a comprehensive written treatment, but Martin Ziegler just gave a tutorial on this at the conference "Computability in Europe". The talks are up on this Youtube channel, specifically "Quantitative Coding and Complexity theory...".

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ It should be said here that Arno is talking about a different correspondence between computability and topology than what the OP linked to. The OP's correspondence is the domain-theoretic one, while Arno is talking about representations by Cantor and Baire spaces. Arguably, the representation approach has a better potential for complexity measures as it is more intensional (it reveals more details about the computation, such as at what location a given piece of information was found, making it easier to establish measures of complexity). $\endgroup$ – Andrej Bauer Jul 1 at 9:09
  • $\begingroup$ @AndrejBauer I would view the domain-theoretic and the representation-based on as two facets of the same correspondence. $\endgroup$ – Arno Jul 1 at 9:16
  • $\begingroup$ As I am sure you know, saying it is "the same correspondence" is a bit hand-wavy. The more precise statement is that there is an adjunction between them. This was in my PhD thesis. $\endgroup$ – Andrej Bauer Jul 1 at 11:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.