Problemy geometryczne, które są NP kompletne w

37

Szereg problemów geometrycznych jest łatwych, gdy rozważa się je w , ale są NP-kompletne w dla (w tym jeden z moich ulubionych problemów, pokrywa dysku jednostki). $R^1$ $R^d$ $d\geq2$

Czy ktoś wie o problemie, który jest polytime rozwiązywalne dla i , ale NP-zupełny dla ? $R^1$ $R^2$ $R^d,d\geq3$

Mówiąc bardziej ogólnie, czy istnieją problemy, które są NP-zupełny dla ale polytime rozwiązywalne dla , gdzie ? $R^k$ $R^{k-1}$ $k\geq3$

cc.complexity-theory reference-request cg.comp-geom

— Bob Fraser
źródło

Czy dopasowanie trójwymiarowe jest geometryczne?

— Jukka Suomela,

1

nie całkiem. „trójwymiarowy” jest kartezjański, a nie euklidesowy.

— Suresh Venkat

25

Ustaw osłonę na pół spacji.

Biorąc pod uwagę zestaw punktów w płaszczyźnie i zestaw półpłaszczyzn obliczający minimalną liczbę półpłaszczyzn pokrywających zestawy punktów, można rozwiązać w czasie wielomianowym w płaszczyźnie. Problemem jest jednak NP trudny w 3d (jest trudniejszy niż znalezienie minimalnej osłony według podzbioru dysków punktów w 2d). W 3d otrzymasz podzbiór półprzestrzeni i punktów i szukasz minimalnej liczby półprzestrzeni pokrywających punkty.

Algorytm czasu policy w 2d jest opisany tutaj: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/

— Sariel Har-Peled
źródło

Jestem trochę zawstydzony, że nie znałem tego wyniku, biorąc pod uwagę, jak blisko są problemy, nad którymi pracuję :-) To jest dokładnie taka odpowiedź, na którą liczyłem. Kiedy mówisz, że jest trudniejszy niż okładka dysku w 2D, myślę, że masz na myśli, że jest to APX-twardy?

— Bob Fraser

1

Problem 2d jest wielomianowy. Drugi to NP-Hard. Jednak nie sądzę, że problem 3D jest trudny w APX. Istnieją dobre powody, by sądzić, że PTAS może być możliwy poprzez wyszukiwanie lokalne ...

— Sariel Har-Peled,

... a trudniej miałem na myśli, że problem z dyskiem można podnieść (tj. zmniejszyć) do problemu półprzestrzeni w 3d.

— Sariel Har-Peled,

29

Nie jest to dokładnie to, o co pytasz, ponieważ wersja 3d jest jeszcze trudniejsza niż NP-complete, ale: Znalezienie najkrótszej ścieżki między dwoma punktami między wielobocznymi przeszkodami w płaszczyźnie odbywa się w czasie wielomianowym (najprościej, zbuduj wykres widoczności dwóch terminali i wierzchołki wielokąta i zastosuj Dijkstrę; istnieje również bardziej skomplikowany algorytm O (n log n) z powodu Hershbergera i Suri, SIAM J. Comput. 1999), ale znalezienie najkrótszej ścieżki między przeszkodami wielościennymi w 3D jest ukończone w PSPACE (Canny i Reif, FOCS 1987).

— David Eppstein
źródło

10

Czy jesteś pewien co do przypadku płaskiego? Algorytmy, które przytaczasz, zasadniczo wymagają dokładnej prawdziwej arytmetyki! cstheory.stackexchange.com/questions/4034/…

— Jeffε

Er. Słuszna uwaga. I nie mogę się z tego wydostać, mówiąc, że używam zmiennoprzecinkowego i przybliżonego, ponieważ problem 3d można dobrze oszacować. Ups Wydaje mi się, że istnieje „dokładna prawdziwa arytmetyka”, w której jeden jest wielomianowy, a drugi trudny, ale nadal masz rację, to inny sposób, w jaki nie odpowiada na pytanie.

— David Eppstein,

6

To jest naprawdę interesujące. Suma problemu z pierwiastkami kwadratowymi przekształca się w szereg problemów w cg, w których problem byłby łatwy, z wyjątkiem tego szczegółu. Jest w pewien sposób świetny, ponieważ jest to jeden z tych problemów, który trzeba przekonać ludzi, że jest trudny. Dzięki za wskazówki.

— Bob Fraser

20

Każdy niewypukły wielokąt w płaszczyźnie może być triangulowany w czasie O (n) bez punktów Steinera; to znaczy każdy wierzchołek triangulacji jest wierzchołkiem wielokąta. Co więcej, każda triangulacja ma dokładnie n-2 trójkątów.

Jednak ustalenie, czy niewypukły wielościan w R ^ 3 może być triangulowany bez punktów Steiner, jest NP-całkowite. Wynik twardości NP zachowuje się nawet wtedy, gdy otrzymasz triangulację z jednym punktem Steiner'a, więc nawet przybliżenie minimalnej liczby wymaganych punktów Steiner jest trudne NP. [Jim Ruppert i Raimund Seidel. O trudnościach triangulacji trójwymiarowej niep wypukłej wielościanu. Discrete Comput. Geom. 1992.]

Jeśli dany wielościan jest wypukły, znalezienie triangulacji jest łatwe, ale znalezienie triangulacji z minimalną liczbą czworościanów jest trudne dla NP. [Alexander Below, Jesús de Loera i Jürgen Richter-Gebert. Złożoność znalezienia małych triangulacji wypukłych 3-polytopów . J. Algorytmy 2004.]

— Jeffε
źródło

2

Dzięki za wskazówki, Jeff. W szczególności uważam, że ostatni wspomniany wynik jest interesujący. Nieco zaskakujące jest to, że w płaszczyźnie liczba uproszczeń składających się na wielokąt jest stała, ale nie ma już większych wymiarów i jest trudna do optymalizacji. To jest dokładnie taka odpowiedź, na którą liczyłem.

— Bob Fraser

16

Problemem wykonalności dla wielowymiarowych wymiarowych jest kandydat. Gdy , to jest on rozwiązany w czasie wielomianowym (według twierdzenia Steinitza ), ale gdy , jest to NP-trudne. Więcej informacji znajduje się w „ Przestrzeniach realizacji 4-polytopów są uniwersalne ” Richtera-Geberta i Zieglera (istnieje również wersja ARXIV ) oraz w książce „ Wykłady o polytopach ” (drugi druk) autorstwa Zieglera. $d$ $d \le 3$ $d \ge 4$

— Yoshio Okamoto
źródło

2

\exists R

$\exists\mathbb{R}$

Dzięki, nie widziałem tego problemu wcześniej.

— Bob Fraser

Ponownie, podobnie jak odpowiedź Davida Eppsteina, trudniejsze (prawdopodobnie) niż NP-zupełne.

— Peter Shor,

11

Decyzja, czy przestrzeń metryczna jest izometrycznie osadzalna w R ^ 2, jest łatwa. Jednak trudno jest zdecydować się na osadzalność R ^ 3.

$\ell_\infty^2$ $\ell_\infty^3$

Papier

— Zouzias
źródło

To także dobry przykład.

— Suresh Venkat

-2

$R^2$ $R^3$ $Z^2$ $Z^3$

$k = 2$ $Z^2$ $Z^k$ $k > 2$ .

— Kaushik Shankar
źródło

co to znaczy powiedzieć, że 2SAT jest „w” R ^ 2?

— Suresh Venkat

R^{2}

$R^2$

11

-1: Nie widzę, jak 2SAT jest w R ^ 2. Nie rozumiem, w jaki sposób 2SAT jest „problemem geometrycznym”.

— Robin Kothari,

Przepraszam, że nie przedstawiłem problemu geometrycznego, ale chociaż tytuł pyta o problemy geometryczne, dwa pytania w komentarzach nie określają, że jest to geometryczny. Ponadto, 2-spełnialność ma reprezentację graficzną znaną jako dopasowanie 2-wymiarowe, to znaczy w P, gdzie jako 3-spełnienie odpowiada dopasowaniu 3-wymiarowemu, czyli NP.

— Kaushik Shankar

@Robin poszedłem naprzód i wyjaśniłem w moim oryginalnym komentarzu.

— Kaushik Shankar