that it is solvable.

Equivariant maps also provide interesting applications of topology to combinatorics. For example, the celebrated result of Lovász on Kneser’s conjecture states that for a graph $G$, the absence of a ${{\mathbb Z}}_2$-equivariant map $B(G) \to S^{n-1}$ imposes a lower bound $\chi(G) \geq n+2$ on the chromatic number of $G$, where $B(G)$ is a certain simplicial complex constructed from $G$, see [@Mat-top].

Building on the work of Brown [@Brown], that is not applicable for $Y=S^{{{n}}-1}$, we investigated in papers [@CKMSVW11; @polypost] the simpler, non-equivariant situation, where $X$ and $Y$ were topological spaces and we were interested in $[X,Y]$, the set of all homotopy classes of continuous maps $X\to Y$. Employing methods of *effective homology* developed by Sergeraert et al. (see e.g. [@SergerGenova]), we showed that for any fixed $d\ge 1$, $[X,Y]$ is polynomial-time computable if $Y$ is $d$-connected and $\dim X\le 2d$. In contrast, [@ext-hard] shows that the problem of computing $[X,Y]$ is \#P-hard when the dimension restriction on $X$ is dropped. More strikingly, a related problem of the existence of a continuous extension of a given map $A \to Y$, defined on a subspace $A$ of $X$, is *undecidable* as soon as $\dim X \geq 2d+2$.

