Abstrakt
(Tento článek je rozšířený abstrakt) Uvažujeme výpočetní problém - nalézt vnoření daného n-bodového metrického prostoru do R^d s nejmenší možnou distorzí, kde d je malá konstanta. Pro d=1 se vědělo, že distorzi nejde aproximovat s faktorem lepším než zhruba n^{1/12}.
Z toho odvodíme neaproximovatelnost pro každé d s faktorem zhruba n^{1/(22d-10)}. Důkaz zahrnuje netriviální výsledek z geometrické topologii, jehož důkaz používá myšlenek J.
Vaisaly. Pro dimenzi 3 a větší ukážeme silnější výsledek jinou redukcí: nelze efektivně odlišit prostory, které se dají vnořit do R^d s konstantní distorzí, od prostorů vyžadujících distorzi aspoň n^{c/d}.