Computing all maps into a sphere

zbMATH Open1421.68162arXiv1105.6257MaRDI QIDQ5743373FDOQ5743373

Authors: Martin Čadek, Marek Krčál, Francis Sergeraert, Lukáš Vokřínek, Jiří Matoušek, Uli Wagner 

Publication date: 10 May 2019

Abstract: Given topological spaces X and Y, a fundamental problem of algebraic topology is understanding the structure of all continuous maps X -> Y . We consider a computational version, where X, Y are given as finite simplicial complexes, and the goal is to compute [X,Y], i.e., all homotopy classes of such maps. We solve this problem in the stable range, where for some d >= 2, we have dim X <= 2d - 2 and Y is (d - 1)-connected; in particular, Y can be the d-dimensional sphere S^d. The algorithm combines classical tools and ideas from homotopy theory (obstruction theory, Postnikov systems, and simplicial sets) with algorithmic tools from effective algebraic topology (locally effective simplicial sets and objects with effective homology). In contrast, [X,Y] is known to be uncomputable for general X,Y, since for X = S^1 it includes a well known undecidable problem: testing triviality of the fundamental group of Y. In follow-up papers, the algorithm is shown to run in polynomial time for d fixed, and extended to other problems, such as the extension problem, where we are given a subspace A of X and a map A -> Y and ask whether it extends to a map X -> Y, or computing the Z_2-index---everything in the stable range. Outside the stable range, the extension problem is undecidable.

Full work available at URL: https://arxiv.org/abs/1105.6257

Recommendations

• Computing all maps into a sphere
• Are two given maps homotopic? An algorithmic viewpoint
• Computing simplicial representatives of homotopy group elements
• Extending continuous maps, polynomiality and undecidability
• Computing simplicial representatives of homotopy group elements

Mathematics Subject Classification ID

Nonnumerical algorithms (68W05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Homotopy groups, general; sets of homotopy classes (55Q05)

Cites Work

• Computational topology. An introduction
• Title not available (Why is that?)
• Title not available (Why is that?)
• Topology for Computing
• Computing all maps into a sphere
• Survey article: an elementary illustrated introduction to simplicial sets
• Title not available (Why is that?)
• Simplification techniques for maps in simplicial topology
• Title not available (Why is that?)
• Products of cocycles and extensions of mappings
• The computability problem in algebraic topology
• Constructive algebraic topology
• Algebraic models for homotopy types
• Hardness of embedding simplicial complexes in \(\mathbb R^d\)
• Cohomology and continuous mappings
• Computability Theory and Differential Geometry
• Algorithmic unsolvability of the triviality problem for multidimensional knots
• Computing spectral sequences
• Title not available (Why is that?)
• Effective algebraic topology
• Title not available (Why is that?)
• Embedding and knotting of manifolds in Euclidean spaces
• Finite computability of Postnikov complexes
• Cohomology operations, and obstructions to extending continuous functions
• Satisfiability of systems of equations of real analytic functions is quasi-decidable
• Title not available (Why is that?)

Cited In (8)

• Computing simplicial representatives of homotopy group elements
• Are two given maps homotopic? An algorithmic viewpoint
• Extendability of continuous maps is undecidable
• Polynomial-time homology for simplicial Eilenberg-MacLane spaces
• Computing all maps into a sphere
• Rational homotopy type and computability
• The computation of megamaps
• Computing homotopy classes for diagrams

This page was built for publication: Computing all maps into a sphere

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5743373)