# computing homotopy type

I'm trying to construct a computer algorithm that decides, whethear a map is homotopically trivial and came to the following question: Let U by a connected closed hypersurface of dimension n-1 that is a union of a finite number of n-1-dimensional "cubes" in $\mathbb{R}^n$. Let L by the set of vertices of these cubes. Let Z be a finite set in $\mathbb{Z}^m-\lbrace 0\rbrace$, $Z=\lbrace (a_1,\ldots,a_m)\neq(0\ldots 0), |a_i|\leq M, a_i\in\mathbb{Z}\rbrace$. Let as define a graph G such that (1) vertices are maps from $U$ fo $\mathbb{R}^m-\lbrace 0\rbrace$, continuous and linear on each "cube face" ($U$ constists of a finite number of cubes) such that f maps the vertices $L$ to the set Z and (2) two vertices $v_1$ and $v_2$ of this graph are connected by an edge (in the graph), iff the map $t v_1 + (1-t)v_2$, $t\in [0,1]$ is to $\mathbb{R}^m-\lbrace 0 \rbrace$. L and Z are finite, so the graph is finite. The question is: are $v_1$ and $v_2$ in a different homotopy classes (as maps from $U$ to $\mathbb{R}^m-\lbrace 0\rbrace\simeq S^{m-1}$) if and only they are in the same connected component of this graph? In other words: if I can connect two piece-wise linear functions by a homotopy, can I connect them by a finite number of "linear homotopies" such that the vertices L are mapped to Z? Or, does it depend on the constant M? Or could you give me some other advice..? Thanks, Peter

-
Such an algorithm would imply a solution to the word problem! – Fernando Muro Feb 8 '11 at 18:10
The following answer may be relevant: mathoverflow.net/questions/51091/computing-homotopies/… . But 2-dimensional rewriting is probably not algorithmically solvable. On the other hand, J.H.C. Whitehead's ideas on Simple Homotopy Theory (SHT) were thought up in terms of generalising to higher dimensions Tietze transformations in group theory. The notions in SHT of expansions and collapses give possible connections with the combinatorial use of "shellability". – Ronnie Brown Mar 20 at 18:15

The answer to your question about replacing homotopies by linear homotopies is yes -- just think through what the Seifert VanKampen theorem says about your 2-complex. The problem is you don't know what linear homotopies to apply as there's too many of them. One of the "killer" linear homotopies is one where you introduce cancelling pairs $gg^{-1}$. You don't know how much longer you need to make a word before you "spot" a relation. That kind of thing.