Speaker: Jennifer Chubb, University of San Francisco
Title: Distance functions on computable graphs

Abstract: A graph is computable if its edge relation is algorithmically decidable. Given two vertices on a connected computable graph, we can ask, "what is the length of the shortest path between them." Of course for a connected graph we can always algorithmically find a path and determine its length, but the question of finding a shortest path is harder and is not in general computable for infinite graphs.

In considering the question of the computational complexity of the distance function on computable graphs, a number of interesting issues arise. We'll begin by looking at effective properties of the family of functions that, like the distance function, have a computable, decreasing approximation. Next, we'll study the specific example of the distance function of a computable graph. We'll see that functions that are computably approximable from above can be coded, in rather a strong sense, into such a distance function, and so this question is, in a sense, as hard as it could possibly be.

This work is joint will Wesley Calvert and Russell Miller.

Department of Mathematical Sciences
George Mason University
4400 University Drive, MS 3F2
Fairfax, VA 22030-4444
http://math.gmu.edu/
Tel. 703-993-1460, Fax. 703-993-1491