2026-08-16T06:32:40Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:16452 2024-03-06T10:57:31Z ddc:004 open_access

Computability of Finite Simplicial Complexes Amir, Djamel Eddine Hoyrup, Mathieu Computable Type Simplicial Complex Surjection Property Topological Cone Absolute Neighborhood Retract Dunce Hat Bing’s House 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 closed manifolds: if a set X is homeomorphic to a sphere or a closed manifold, 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, Iljazović, Sušić and others in the recent years. A similar notion of computable type was also defined for pairs (X,A) in order to cover more spaces, such as compact manifolds with boundary and finite graphs with endpoints. We investigate the higher dimensional analog of graphs, namely the pairs (X,A) where X is a finite simplicial complex and A is a subcomplex of X. We give two topological characterizations of the pairs having computable type. The first one uses a global property of the pair, that we call the ε-surjection property. The second one uses a local property of neighborhoods of vertices, called the surjection property. We give a further characterization for 2-dimensional simplicial complexes, by identifying which local neighborhoods have the surjection property. Using these characterizations, we give non-trivial applications to two famous sets: we prove that the dunce hat does not have computable type whereas Bing’s house does. Important concepts from topology, such as absolute neighborhood retracts and topological cones, play a key role in our proofs. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Djamel Eddine Amir and Mathieu Hoyrup 2022 Is Part Of LIPIcs, Volume 229, 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.ICALP.2022.111 urn:nbn:de:0030-drops-164522 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2022.111 eng https://creativecommons.org/licenses/by/4.0/legalcode