×

zbMATH — the first resource for mathematics

Extendability of continuous maps is undecidable. (English) Zbl 1358.68297
Summary: We consider two basic problems of algebraic topology: the extension problem and the computation of higher homotopy groups, from the point of view of computability and computational complexity.
The extension problem is the following: Given topological spaces \(X\) and \(Y\), a subspace \(A\subseteq X\), and a (continuous) map \(f:A\rightarrow Y\), decide whether \(f\) can be extended to a continuous map \(\bar{f}: X\to Y\). All spaces are given as finite simplicial complexes, and the map \(f\) is simplicial.
Recent positive algorithmic results, proved in a series of companion papers, show that for \((k - 1)\)-connected \(Y\), \(k\geq 2\), the extension problem is algorithmically solvable if the dimension of \(X\) is at most \(2k - 1\), and even in polynomial time when \(k\) is fixed.
Here we show that the condition \(\dim X\leq 2k-1\) cannot be relaxed: for \(\dim X=2k\), the extension problem with \((k - 1)\)-connected \(Y\) becomes undecidable. Moreover, either the target space \(Y\) or the pair \((X,A)\) can be fixed in such a way that the problem remains undecidable.
Our second result, a strengthening of a result of D. J. Anick [Lect. Notes Pure Appl. Math. 114, 1–56 (1989; Zbl 0691.55009)], says that the computation of \(\pi _{k }(Y)\) of a 1-connected simplicial complex \(Y\) is #P-hard when \(k\) is considered as a part of the input.

MSC:
68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
03D35 Undecidability and degrees of sets of sentences
55Q52 Homotopy groups of special spaces
55U10 Simplicial sets and complexes in algebraic topology
68Q17 Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)
68Q25 Analysis of algorithms and problem complexity
PDF BibTeX Cite
Full Text: DOI
References:
[1] Adams, J.F., On the cobar construction, Proc. Natl. Acad. Sci. USA, 42, 409, (1956) · Zbl 0071.16404
[2] Anick, D.J., The computation of rational homotopy groups is #℘-hard, Proc. Conf., Chicago, IL, 1986
[3] Bredon, G.: Topology and Geometry. Graduate Texts in Mathematics, vol. 139. Springer, Berlin (1993) · Zbl 0791.55001
[4] Brown, E.H., Finite computability of postnikov complexes, Ann. Math. (2), 65, 1-20, (1957) · Zbl 0077.16804
[5] Čadek, M., Krčál, M., Matoušek, J., Sergeraert, F., Vokřínek, L., Wagner, U.: Computing all maps into a sphere. arXiv:1105.6257 (2011). Extended abstract in Proc. ACM-SIAM Symposium on Discrete Algorithms (SODA 2012)
[6] Čadek, M., Krčál, M., Matoušek, J., Vokřínek, L., Wagner, U.: Polynomial-time computation of homotopy groups and Postnikov systems in fixed dimension. arXiv:1211.3093 (2012)
[7] Fritsch, R., Piccinini, R.A.: Cellular Structures in Topology. Cambridge Studies in Advanced Mathematics, vol. 19. Cambridge University Press, Cambridge (1990) · Zbl 0837.55001
[8] Friedman, G., An elementary illustrated introduction to simplicial sets, Rocky Mt. J. Math., 42, 353-423, (2012) · Zbl 1248.55001
[9] Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2001). Electronic version available at http://math.cornell.edu/hatcher#AT1 · Zbl 1044.55001
[10] Hilton, J.P., On the homotopy groups of union of spheres, J. Lond. Math. Soc., 3, 154-172, (1955) · Zbl 0064.17301
[11] Jardine, J.F., Simplicial approximation, Theory Appl. Categ., 12, 34-72, (2004) · Zbl 1062.55019
[12] Krčál, M., Matoušek, J., Sergeraert, F.: Polynomial-time homology for simplicial Eilenberg-MacLane spaces. arXiv:1201.6222 (2011). J. Found. Comput. Math. (to appear)
[13] Kochman, S.O.: Stable Homotopy Groups of Spheres. A Computer-Assisted Approach. Lecture Notes in Mathematics, vol. 1423. Springer, Berlin (1990) · Zbl 0688.55010
[14] Matiyasevich, Yu., The diophantineness of enumerable sets, Dokl. Akad. Nauk SSSR, 191, 279-282, (1970)
[15] Matiyasevich, Y.V.: Hilbert’s Tenth Problem. Foundations of Computing Series. MIT Press, Cambridge (1993). Translated from the 1993 Russian original by the author, with a foreword by Martin Davis
[16] May, J.P.: Simplicial Objects in Algebraic Topology. Chicago Lectures in Mathematics. University of Chicago Press, Chicago (1992). Reprint of the 1967 original; the page numbers do not quite agree with the 1967 edition · Zbl 0769.55001
[17] Mazur, B., Questions of decidability and undecidability in number theory, J. Symb. Log., 59, 353-371, (1994) · Zbl 0814.11059
[18] Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Reading (1984) · Zbl 0673.55001
[19] Novikov, P.S., Ob algoritmičeskoĭ nerazrešimosti problemy toždestva slov v teorii grupp (on the algorithmic unsolvability of the word problem in group theory), Tr. Mat. Inst. Steklova, 44, 1-143, (1955)
[20] Nabutovsky, A.; Weinberger, S., Algorithmic unsolvability of the triviality problem for multidimensional knots, Comment. Math. Helv., 71, 426-434, (1996) · Zbl 0862.57017
[21] Nabutovsky, A.; Weinberger, S., Algorithmic aspects of homeomorphism problems, No. 231, 245-250, (1999), Providence · Zbl 0932.57021
[22] Ravenel, D.C.: Complex Cobordism and Stable Homotopy Groups of Spheres, 2nd edn. Am. Math. Soc., Providence (2004) · Zbl 1073.55001
[23] Real, P., An algorithm computing homotopy groups, Math. Comput. Simul., 42, 461-465, (1996) · Zbl 1037.55502
[24] Romero, A.; Rubio, J.; Sergeraert, F., Computing spectral sequences, J. Symb. Comput., 41, 1059-1079, (2006) · Zbl 1132.55008
[25] Rubio, J.; Sergeraert, F., Constructive algebraic topology, Bull. Sci. Math., 126, 389-412, (2002) · Zbl 1007.55019
[26] Rubio, J.; Sergeraert, F., Algebraic models for homotopy types, Homol. Homotopy Appl., 17, 139-160, (2005) · Zbl 1088.55006
[27] Rubio, J., Sergeraert, F.: Constructive homological algebra and applications. arXiv:1208.3816 (2012). Written in 2006 for a MAP Summer School at the University of Genova
[28] Schön, R., Effective algebraic topology, Mem. Am. Math. Soc., 451, 63, (1991) · Zbl 0731.55015
[29] Sergeraert, F., The computability problem in algebraic topology, Adv. Math., 104, 1-29, (1994) · Zbl 0823.55011
[30] Smith, J.R.: m-Structures determine integral homotopy type. arXiv:math/9809151v1 (1998)
[31] Soare, R.I., Computability theory and differential geometry, Bull. Symb. Log., 10, 457-486, (2004) · Zbl 1085.03033
[32] Spanier, E.H.: Algebraic Topology. McGraw-Hill, New York (1966) · Zbl 0145.43303
[33] Steenrod, N.E., Cohomology operations, and obstructions to extending continuous functions, Adv. Math., 8, 371-416, (1972) · Zbl 0236.55018
[34] Whitehead, G.W.: Elements of Homotopy Theory. Graduate Texts in Mathematics, vol. 61. Springer, New York (1978) · Zbl 0406.55001
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.