Jonathan Spreer: Parametrized complexity of simple homotopy

Deciding whether two simplicial complexes are homotopy equivalent is a fundamental problem in topology, which is undecidable already for contractible 2-complexes. There exists a combinatorial refinement of this concept, called simple-homotopy: two simplicial complexes are of the same simple-homotopy type if they can be transformed into each other by a sequence of two basic homotopy equivalences, an elementary collapse and its inverse, an elementary expansion.

In my talk I will explain the notions necessary to obtain a basic understanding of simple homotopy equivalences. I will then go on to sketch a computational hardness result for the following problem: given a 2-dimensional simplicial complex C, is there a simple-homotopy equivalence from C to a 1-dimensional simplicial complex using at most p expansions followed only by collapses? The interest in this particular variant of the simple homotopy equivalence problem is motivated by the fact that introducing the bound p renders the problem decidable.