# Computing higher homotopy groups is W[1]-hard

arXiv: https://arxiv.org/abs/1304.7705 · HTML: https://mlsanity.com/paper/1304.7705/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 29 Apr 2013.

## Built on by (most cited first, 1 of 1)

- [Universal Approximation Theorems for Differentiable Geometric Deep Learning](https://mlsanity.com/paper/2101.05390/) (2021)

## Abstract (arXiv)

Recently it was shown that, for every fixed k>1, given a finite simply connected simplicial complex X, the kth homotopy group πk(X) can be computed in time polynomial in the number n of simplices of X. We prove that this problem is W[1]-hard w.r.t. the parameter k even for X of dimension 4, and thus very unlikely to admit an algorithm with running time bound f(k)nC for an absolute constant C. We also simplify, by about 20 pages, a 1989 proof by Anick that, with k part of input, the computation of the rank of πk(X) is #P-hard.