Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension

Investor logo

Warning

This publication doesn't include Faculty of Medicine. It includes Faculty of Science. Official publication website can be found on muni.cz.
Authors

ČADEK Martin KRČÁL Marek MATOUŠEK Jiří VOKŘÍNEK Lukáš WAGNER Uli

Year of publication 2014
Type Article in Periodical
Magazine / Source SIAM Journal on Computing
MU Faculty or unit

Faculty of Science

Citation
Web http://dx.doi.org/10.1137/120899029
Doi http://dx.doi.org/10.1137/120899029
Field General mathematics
Keywords homotopy groups; Postnikov systems; computational complexity
Description For several computational problems in homotopy theory, we obtain algorithms with running time polynomial in the input size. In particular, for every fixed integer k, there is a polynomial-time algorithm that, for a one-connected topological space given as a simplicial set with polynomial-time homology, computes its k-th homotopy group, as well as the first k stages of its Postnikov system.
Related projects:

You are running an old browser version. We recommend updating your browser to its latest version.

More info