# 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 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.