Descriptive complexity on non-Polish spaces II

Mathieu Hoyrup (1)

1 MOCQUA - Designing the Future of Computational Models

This article is a study of descriptive complexity of subsets of represented spaces. Two competing measures of descriptive complexity are available. The first one is topological and measures how complex it is to obtain a set from open sets using boolean operations. The second one measures how complex it is to test membership in the set, and we call it symbolic complexity because it measures the complexity of the symbolic representation of the set. While topological and symbolic complexity are equivalent on countably-based spaces, they differ on more general spaces. Our investigation is aimed at explaining this difference and highly suggests that it is related to the well-known mismatch between topological and sequential aspects of topological spaces.

Domaines: Logique en informatique [cs.LO]; Topologie générale [math.GN]

Mathieu Hoyrup. Descriptive complexity on non-Polish spaces II. ICALP, Jul 2020, Saarbrücken, Germany. ⟨10.4230/LIPIcs.ICALP.2020.132⟩. ⟨hal-02483114⟩