Applications of Topology to Lower Bound Estimates in Computer Science

This research explores the relationship between topology and computer science by analyzing simple problems in which the role played by topology is crucial, yet which can be approached using techniques that are not too esoteric. The goal is to develop a set of topological tools which can then be applied to other, more central, problems in complexity theory.We define the concepts of "a problem" and "problem reduction" in computer science in such a way as to make the techniques of point set and algebraic topology applicable. Following Smale, we define "topological complexity" as the minimal number of branch nodes in an algebraic computation tree and relate it to the Schwartz genus of a map.We introduce a new problem, the new point problem (NPP), and calculate its topological complexity for a variety of spaces. NPP has many variations. The most realistic and applicable version is the following. Given a list of n distinct points in a metric space X with a known lower bound delta for the distance between any two points, what is the topological complexity of finding a new point y such that delta is still a lower bound for the distance between any two points.We prove: TheoremThe topological complexity of the above problem on the interval [0,1], with n sufficiently small, is n.In the final chapter, we show how to use the definition of "a problem" to get lower bounds on the non-linear complexity of many problems in Computer Science that are slightly better than previous lower bounds.

ICSI Technical Report TR-90-019

Technical Report