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

A map $f\colon K\to \mathbb{R}^d$ of a simplicial complex is an almost embedding if $f(\sigma)\cap f(\tau)=\emptyset$ whenever $\sigma,\tau$ are disjoint simplices of $K$.
Theorem. {\it For each integers $d,k\ge2$ such that $d=\frac{3k}2+1$ the algorithmic problem of recognition embeddability (almost embeddability) of finite $k$-dimensional complexes in $\mathbb{R}^d$ is NP hard.}
This talk will be accessible to non-specialists. I will describe motivations and ideas of proof of this result, including singular versions of Higher-dimensional Borromean Rings Lemma and Generalized Van Kampen-Flores Theorem.
(On joint work with Martin Tancer and on Matoušek-Tancer-Wagner work)