A machine processing Klein bottles into strings of bits.

Descriptive complexity on represented spaces

In the framework of Type-2 Theory of Effectivity (TTE), represented spaces (topological spaces equipped with a representation) form a general context in which computability has been extended.

Descriptive Set Theory (DST) provides two competing measures of complexity for sets in such spaces. The first one is topological, and stratifies sets according to the number of Boolean operations required to obtain them from open sets. The second one measures the complexity of effectively testing membership in the set. As it measures the complexity of the symbolic representation of the set, we call it the symbolic complexity.

In this talk, we investigate these two measures of complexity. While they coincide on countably-based spaces (as proved in [De Brecht, 2012]), topological and symbolic complexity may differ on more general spaces. We suggest that this difference is related to the mismatch between topological and sequential aspects of the topology of these spaces.

Acknowledgments: This talk is based on joint work with Mathieu Hoyrup, started in this article and continued in its sequel.