Small Model $2$-Complexes in $4$-space and Applications

We consider computational complexity of problems related to the fundamental group and the first homology group of (embeddable) $2$-complexes. We show, as an extension of an earlier work, that computing first homology of $2$-complexes is equivalent in computational complexity to matrix diagonalization. That is, the usual procedures for computing homology cannot be improved other than by matrix methods. This is true even if the complex is in the euclidean $4$-space. For this purpose, we use $2$-complexes built in a standard way from group presentations, called model $2$-complexes. Model complexes have fundamental group isomorphic with the group defined by the presentation. We show that there are model complexes of size in the order of the bit-complexity of the presentation that can be realized linearly in $4$-space. We further derive some applications of this result regarding embeddability problems in the euclidean $4$-space.