---
_id: '2184'
abstract:
- lang: eng
  text: 'Given topological spaces X,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], that is, all homotopy classes of suchmaps.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 Sd. 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 = S1 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 ⊂ X and a map A→ Y and ask whether it extends to a map X → Y, or
    computing the Z2-index-everything in the stable range. Outside the stable range,
    the extension problem is undecidable.'
acknowledgement: The research by M. K. was supported by project GAUK 49209. The research
  by M. K. was also supported by project 1M0545 by the Ministry of Education of the
  Czech Republic and by Center of Excellence { Inst. for Theor. Comput. Sci., Prague
  (project P202/12/G061 of GACR). The research by U. W. was supported by the Swiss
  National Science Foundation (SNF Projects 200021-125309, 200020-138230, and PP00P2-138948).
article_number: '17 '
article_processing_charge: No
arxiv: 1
author:
- first_name: Martin
  full_name: Čadek, Martin
  last_name: Čadek
- first_name: Marek
  full_name: Krcál, Marek
  id: 33E21118-F248-11E8-B48F-1D18A9856A87
  last_name: Krcál
- first_name: Jiří
  full_name: Matoušek, Jiří
  last_name: Matoušek
- first_name: Francis
  full_name: Sergeraert, Francis
  last_name: Sergeraert
- first_name: Lukáš
  full_name: Vokřínek, Lukáš
  last_name: Vokřínek
- first_name: Uli
  full_name: Wagner, Uli
  id: 36690CA2-F248-11E8-B48F-1D18A9856A87
  last_name: Wagner
  orcid: 0000-0002-1494-0568
citation:
  ama: Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing
    all maps into a sphere. <i>Journal of the ACM</i>. 2014;61(3). doi:<a href="https://doi.org/10.1145/2597629">10.1145/2597629</a>
  apa: Čadek, M., Krcál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., &#38; Wagner,
    U. (2014). Computing all maps into a sphere. <i>Journal of the ACM</i>. ACM. <a
    href="https://doi.org/10.1145/2597629">https://doi.org/10.1145/2597629</a>
  chicago: Čadek, Martin, Marek Krcál, Jiří Matoušek, Francis Sergeraert, Lukáš Vokřínek,
    and Uli Wagner. “Computing All Maps into a Sphere.” <i>Journal of the ACM</i>.
    ACM, 2014. <a href="https://doi.org/10.1145/2597629">https://doi.org/10.1145/2597629</a>.
  ieee: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, and U. Wagner,
    “Computing all maps into a sphere,” <i>Journal of the ACM</i>, vol. 61, no. 3.
    ACM, 2014.
  ista: Čadek M, Krcál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2014. Computing
    all maps into a sphere. Journal of the ACM. 61(3), 17.
  mla: Čadek, Martin, et al. “Computing All Maps into a Sphere.” <i>Journal of the
    ACM</i>, vol. 61, no. 3, 17, ACM, 2014, doi:<a href="https://doi.org/10.1145/2597629">10.1145/2597629</a>.
  short: M. Čadek, M. Krcál, J. Matoušek, F. Sergeraert, L. Vokřínek, U. Wagner, Journal
    of the ACM 61 (2014).
date_created: 2018-12-11T11:56:12Z
date_published: 2014-05-01T00:00:00Z
date_updated: 2025-09-29T11:34:15Z
day: '01'
department:
- _id: UlWa
- _id: HeEd
doi: 10.1145/2597629
external_id:
  arxiv:
  - '1105.6257'
  isi:
  - '000337201400003'
fulldoi: https://doi.org/10.1145/2597629
intvolume: '        61'
isi: 1
issue: '3'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: http://arxiv.org/abs/1105.6257
month: '05'
oa: 1
oa_version: Preprint
publication: Journal of the ACM
publication_status: published
publisher: ACM
publist_id: '4797'
quality_controlled: '1'
scopus_import: '1'
status: public
title: Computing all maps into a sphere
type: journal_article
user_id: 317138e5-6ab7-11ef-aa6d-ffef3953e345
volume: 61
year: '2014'
...