论文标题
$ \ mathbb {r}^d $，ii几乎嵌入简单复合物的硬度
Hardness of almost embedding simplicial complexes in $\mathbb{R}^d$, II
论文作者
论文摘要
如果$ f（σ）\ cap f（τ）= \ varnothing $，a map $ f：k \ to \ mathbb {r}^d $几乎是嵌入的，则只要$ f（每当$σ，τ$都是$ k $的差异简单）。修复整数$ d，k \ geqslant 2 $，以便$ k+2 \ leqslant d \ leqslant \ frac {3k} 2+1 $。假设“一个周期的预映射是一个周期”，我们证明$ \ mathbf {np} $ - 识别有限$ k $二维复合物几乎嵌入性的算法问题的硬度。假设$ \ mathbf {p} \ ne \ ne \ mathbf {np} $（并且“一个周期的预映射是一个周期”），我们证明，嵌入障碍物对于$ k $ dimensional complextion不完整，对于$ \ \ \ \ \ \ \ mthbb {r}^d $ in Confipururation supporturation space而言。我们的证明概括了Skopenkov-tancer的证明此结果的证明，$ d = \ frac {3k} {2} {2} + 1 $。
A map $f: K \to \mathbb{R}^d$ of a simplicial complex is an almost embedding if $f(σ) \cap f(τ) = \varnothing$ whenever $σ, τ$ are disjoint simplices of $K$. Fix integers $d,k \geqslant 2$ such that $k+2 \leqslant d \leqslant\frac{3k}2+1$. Assuming that the "preimage of a cycle is a cycle" we prove $\mathbf{NP}$-hardness of the algorithmic problem of recognition of almost embeddability of finite $k$-dimensional complexes in $\mathbb{R}^d$. Assuming that $\mathbf{P} \ne \mathbf{NP}$ (and that the "preimage of a cycle is a cycle") we prove that the embedding obstruction is incomplete for $k$-dimensional complexes in $\mathbb{R}^d$ using configuration spaces. Our proof generalizes the Skopenkov-Tancer proof of this result for $d = \frac{3k}{2} + 1$.
