2022/06/27 by Alkin, Emil
#57Q35 #68Q17 #Combinatorics (math.CO) #Computational Complexity (cs.CC) #Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences #FOS: Mathematics #Geometric Topology (math.GT)
paper · doi:10.48550/arxiv.2206.13486
A map f: K → ℝd of a simplicial complex is an almost embedding if f(σ) ∩ f(τ) = \varnothing whenever σ, τ are disjoint simplices of K. Fix integers d,k \geqslant 2 such that k+2 \leqslant d \leqslant\frac3k2+1. Assuming that the "preimage of a cycle is a cycle" we prove NP-hardness of the algorithmic problem of recognition of almost embeddability of finite k-dimensional complexes in ℝd. Assuming that P ≠ NP (and that the "preimage of a cycle is a cycle") we prove that the embedding obstruction is incomplete for k-dimensional complexes in ℝd using configuration spaces. Our proof generalizes the Skopenkov-Tancer proof of this result for d = (3k)/(2) + 1.