Abstrakt
Nechť EMBED_{k --} d} značí následující algoritmický problém: je-li zadán simpliciální komplex K dimenze nejvýše k, existuje jeho po částech lineární vnoření do R^d? Známe výsledky implikují, že tento problém je řešitelný v polynomiálním čase pro situace EMBED_{1 --} 2}, EMBED_{2--}2} a EMBED_{k --} 2k} pro k alespoň 3 (dokonce pokud k není pevné). V článku ukazujeme, že slavná Novikova věta o algoritmické nerzhodnutelnosti rozpoznávání 5-sféry implikuje, že EMBED_{d --} d} a EMBED_{(d-1) --} d} jsou nerozhodnutelné pro každé d alespoň 5.
Hlavním výsledkem je NP-těžkost situace EMBED_{2 --} 4} a obecněji situace EMBED_{k --} d}, kde d je alespoň 4 a d }= k }= (2d-2)/3.