Distance functions on computable graphs

Consider a connected infinite graph.  A natural question one might ask about a given pair of vertices on the graph is, “What’s the shortest path between these two nodes?”  We study the algorithmic complexity of this question for computable graphs (a graph is computable if its edge relation is algorithmically decidable).  Specifically, we define the distance function for a graph (it is what you think it is) and discover some interesting properties.  In fact, we’ll see algorithmic properties of a whole family of functions that, like the distance function, have a computable decreasing approximation (that is also probably what you think it is).  In the end, we’ll be able to encode complex information into the structure of a graph so that the corresponding distance function is computationally as hard as it could possibly be.

This work is joint with Wesley Calvert and Russell Miller.