  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.
