NP-трудность вложимости и почти вложимости гиперграфов в $\mathbb R^d$

A map $f:K\to\mathbb R^d$ of a simplicial complex is an almost embedding if $f(\sigma)\cap f(\tau)=\emptyset$ whenever $\sigma$ and $\tau$ are disjoint simplices of $K$.
Theorem. Fix integers $d,k\ge 2$ such that $d=3k/2+1$.
(a) Assume that $P\neq NP$. Then there exists a finite $k$-dimensional complex $K$ that does not admit an almost embedding in $\mathbb R^d$ but for which there exists an equivariant map $K\times K\setminus \Delta(K) \to S^{d-1}$. (b) The algorithmic problem of recognition almost embeddability of finite $k$-dimensional complexes in $\mathbb R^d$ is NP-hard.
The proof is based on the technique from the Matoušek–Tancer–Wagner paper (proving an analogous result for embeddings), and on singular versions of the higher-dimensional Borromean rings lemma and a generalized van Kampen–Flores theorem.