Najlepszy sposób na określenie minimalnego wymiaru konstrukcji, biorąc pod uwagę tylko odległości między punktami

Zetknąłem się z tym problemem w dziedzinie fizyki dość dalekiej od informatyki, ale wydaje się, że jest to pytanie, które było badane w CS, więc pomyślałem, że spróbuję szczęścia, zadając to tutaj.

Wyobraź sobie, że otrzymałeś zestaw punktów oraz listę niektórych odległości między punktami d i j . Jaki jest najskuteczniejszy sposób określenia minimalnej wymiarowości przestrzeni, w której należy osadzić te punkty? Innymi słowy, co jest najmniejszym k, tak że istnieje zbiór punktów w R k spełniający ograniczenia odległości d i j . Byłbym równie zadowolony z odpowiedzi dla C k , ale wydaje się to trudniejsze.$\{v_i\}_{i=1}^n$$d_{ij}$$k$$\mathbb{R}^k$$d_{ij}$$\mathbb{C}^k$

Z przyjemnością stwierdzam, że odległości muszą się zgadzać tylko z pewną stałą dokładnością ϵ i ograniczać punkty do punktów na pewnej sieci stałej odległości, aby uniknąć problemów z obliczeniami z rzeczywistością.$d_{ij}$$\epsilon$

Rzeczywiście, byłbym całkiem zadowolony z rozwiązania dla decyzyjnej wersji tego problemu, w którym biorąc pod uwagę i k , pytamy cię, czy istnieje taki zestaw wierzchołków { v i } . Problem jest w NP, ponieważ biorąc pod uwagę zestaw punktów w R k , łatwo jest sprawdzić, czy spełniają wymagania dotyczące odległości, ale wydaje się, że dla tego konkretnego problemu powinny istnieć algorytmy sub-wykładnicze.$d_{ij}$$k$$\{v_i\}$$\mathbb{R}^k$

$k$

Na koniec powiem, że wiem, że łatwo jest tworzyć listy odległości, których nie można spełnić w żadnej liczbie wymiarów (tj. Takich, które naruszają nierówność trójkąta). Jednak dla przypadków, na których mi zależy, zawsze będzie jakaś minimalna skończona liczba wymiarów, w których można znaleźć zadowalający zestaw punktów.

Problem ten jest czasem nazywany uzupełnianiem macierzy odległości w niskim wymiarze euklidesowym lub osadzaniem wykresu ważonego w niskim wymiarze euklidesowym.

Saxe [Sax79] i Yemini [Yem79] niezależnie wykazali poprzez proste zmniejszenie problemu Partition, że problem ten jest NP-zupełny nawet w przypadku jednego wymiaru; to znaczy, następujący problem jest NP-zupełny dla k = 1:

k- wymiarowe uzupełnienie macierzy odległości euklidesowej / k- wymiarowe osadzenie euklidesowe wykresu ważonego
Instancja : macierz symetryczna M, której wpisy są dodatnimi liczbami całkowitymi w postaci binarnej lub „nieznane”.
Pytanie : Czy nieznane wpisy w M można wypełnić liczbami rzeczywistymi, aby M stał się macierzą odległości punktów w k- wymiarowej przestrzeni euklidesowej ℝ ^k ?
Równoważnie:
Instancja : Wykres G, gdzie każda krawędź ma dodatnią wagę całkowitą zapisaną binarnie.
Pytanie : Czy wierzchołki G umieszczone wk - wymiarowa przestrzeń euklidesowa ℝ ^k tak, aby dla każdej krawędzi G odległość między dwoma punktami końcowymi była równa ciężarowi krawędzi?

Co więcej, Saxe [Sax79] wykazał (przez bardziej zaangażowane zmniejszenie z 3SAT), że k- wymiarowe uzupełnienie macierzy odległości euklidesowej pozostaje NP-twarde nawet pod ograniczeniem, że wszystkie znane wpisy w M wynoszą 1 lub 2, dla każdej dodatniej stałej całkowitej k . W szczególności problem jest NP-zupełny, nawet jeśli znane wpisy w M są podane pojedynczo. [Sax79] zawiera również wyniki dotyczące twardości dotyczące przybliżonego osadzania.

Nawiasem mówiąc, nie sądzę, że to jest trywialne, że problem dotyczy NP; zwróć uwagę, że potrzebujesz nieracjonalnych współrzędnych w niektórych przypadkach, gdy k > 1. Nie wiem, czy wiadomo, że jest w NP.

Bibliografia

[Sax79] James B. Saxe. Osadzanie ważonych wykresów w przestrzeni k jest silnie trudne dla NP. W materiałach z 17. Konferencji Allerton na temat komunikacji, kontroli i informatyki , s. 480–489, 1979. Również w James B. Saxe: Dwa dokumenty o problemach z osadzaniem wykresów , Wydział Informatyki, Carnegie-Mellon University, 1980.

[Yem79] Yechiam Yemini. Niektóre teoretyczne aspekty problemów z pozycjonowaniem pozycji. W 20. dorocznym sympozjum na temat podstaw informatyki (FOCS) , s. 1–8, październik 1979 r. DOI: 10.1109 / SFCS.1979.39

$d$$n$$d$$n$