Computing higher homotopy groups is W[1]-hard

2013/04/29 by Jiřı́ Matoušek, Matousek, Jiri
Computer Science · Mathematics · #55Q05 #68U05 #68W99 #Algebraic structures and combinatorial models #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #FOS: Computer and information sciences #Homotopy and Cohomology in Algebraic Topology #Topological and Geometric Data Analysis

paper · pdf · doi:10.48550/arxiv.1304.7705

openalex publication_date 2013/04/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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)n^C 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.

Citations

• Constructive Homological Algebra and Applications
• Polynomial-time computation of homotopy groups and Postnikov systems in\n fixed dimension

Related

• Computing simplicial representatives of homotopy group elements
• Polynomial-time computation of homotopy groups and Postnikov systems in\n fixed dimension
• Finding Bounded Simplicial Sets with Finite Homology
• Annotating Simplices with a Homology Basis and Its Applications
• Efficient simplicial replacement of semi-algebraic sets