Topology Atlas Conference Abstracts Document # caai-92.htm | Production Editor: J. Schommer

The Eighth Prague Topological Symposium
August 18-24, 1996
Economical University
Prague, Czech Republic
Continuous Algorithms

by

Michael D. Rice
(Wesleyan University )


Many of the established connections between topology and computer science involve the interplay of order-theoretic ideas and "non-classical" topological spaces with weak separation properties. Recently, I have been investigating the continuity (with respect to Euclidean topologies) of elementary algorithms that are widely used in computer science. In many situations, an algorithm's correctness guarantees that it will not compute a continuous function. This is the case for search algorithms or for an algorithm that computes the two nearest points in a set of points in the plane. On the other hand, an algorithm that correctly sorts sequences of real numbers of length N computes a Lipschitz mapping on Euclidean N-space.

I have found that for a certain class of algorithms, the assumption that a member computes a continuous function between Euclidean spaces is surprisingly restrictive. Roughly speaking, this class consists of algorithms where the output data is a subset of the input data that depends on its order-theoretic structure. The familiar algorithms used for sorting and for computing an order-statistic are members of this class.

The lecture will present several results establishing that certain algorithms in the above class can compute only finitely many distinct continuous mappings. Therefore, in these cases, it may be possible to design decision procedures for establishing the "discontinuity of an algorithm". The proof techniques have also been used to establish a topological version of the 0-1 Sorting Lemma (under certain conditions an algorithm that correctly sorts sequences of 0's and 1's correctly sorts all sequences).


Received by the editors: June 24, 1996.

Conference Archive | Conference Abstracts