Résumé :

The topological properties of a set have a strong impact on its computability properties. A striking illustration of this idea is given by spheres and finite graphs without endpoints: if a set X is homeomorphic to a sphere or a such graph, then any algorithm that semicomputes X in some sense can be converted into an algorithm that fully computes X. In other words, the topological properties of X enable one to derive full information about X from partial information about X. In that case, we say that X has computable type. Those results have been obtained by Miller and Iljazović in the recent years. We give a characterization of finite simplicial complexes having computable type using a local property of stars of vertices. Moreover, the reduction to homology implies that the computable type property is decidable, for finite simplicial complexes of dimension at most 4. We argue that the stronger, relativized version of computable type, is better behaved. Consequently, we obtain characterizations of strong computable type, related to the descriptive complexity of topological invariants. This leads us to investigate the expressive power of low complexity invariants in the Borel hierarchy and their ability to differentiate between spaces. Notably, we show that they are sufficient for distinguishing finite topological graphs.