Polynomial-Time Computation of Homotopy Groups and Postnikov Systems in Fixed Dimension
| Authors | |
|---|---|
| Year of publication | 2014 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Computing |
| MU Faculty or unit | |
| 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: |