Jakie problemy w geometrii obliczeniowej lub teorii grafów uważa się za

12

Jest to pytanie uzupełniające do poprzedniego postu Robina Kothari na temat wyników twardości wielomianowej .

Interesuje mnie w szczególności sprawdzenie niektórych dowodów twardości dla problemów, które mają z grubsza dolne granice, i mówię z grubsza, aby pozwolić na nieco subkubiczne ulepszenia, grając z rozmiarem słowa (np. 3SUM autorstwa Barab i wsp. [Przez Springera] ). Z przyjemnością utrzymam problemy w modelu drzewa decyzyjnego, jeśli uprości to odpowiedzi. $\Omega(n^3)$

Z postu Robina dowiedziałem się o artykule Jeffa Eriksona, który podaje dolną granicę dla 5SUM (dokładniej pokazuje, że SUM działa w czas w ogóle). $\Omega(n^3)$ $k$ $\Omega (n^{\lceil k/2 \rceil})$

Czy istnieją papiery lub inne odnośniki wykorzystujące takie redukcje do przypuszczenia sześciennych dolnych granic dla problemów w geometrii obliczeniowej lub teorii grafów?

graph-theory cg.comp-geom lower-bounds

— Bob Fraser
źródło

Obie odpowiedzi były dla mnie pomocne, dzięki! Doceniono także wskaźnik Jeffa do pracy Timothy'ego, co jest bardzo dobrym wynikiem.

— Bob Fraser

13

Myślę, że artykuł pod tytułem „ Podkubiczne równoważności problemów ścieżki, macierzy i trójkąta ” autorstwa V. Vassilevskiej Williams i R. Williamsa jest tym, czego szukasz. Jego streszczenie zawiera listę następujących problemów na wykresach:

Problem wszystkich par najkrótszych ścieżek na ważonych digrafach (APSP).
Wykrywanie, czy wykres ważony ma trójkąt o ujemnej całkowitej masie krawędzi.
Lista do trójkątów ujemnych na wykresie ważonym na krawędzi. $n^{2.99}$
Problem ścieżek zastępczych na ważonych digrafach.
Znalezienie drugiej najkrótszej prostej ścieżki między dwoma węzłami w ważonym digrafie.

Według streszczenia artykuł dotyczy następujących zagadnień:

Definiujemy pojęcie subkubicznej redukowalności i pokazujemy, że wiele ważnych problemów na wykresach i macierzach możliwych do rozwiązania w czasie jest równoważnych w ramach redukcji subkubicznych. $O(n^3)$

— Oleksandr Bondarenko
źródło

6

Ale zobacz także subububny algorytm APSP Timothy'ego Chana, który NIE gra w gry bitowe: springerlink.com/content/px2741688g4p4l18

— Jeffε

9

Następnie można użyć redukcji tego problemu jako punktu wyjścia do udowodnienia dolnych granic. Patrz na przykład sekcja 5 w następującym dokumencie: http://valis.cs.uiuc.edu/~sariel/papers/03/lms/lms.pdf . Również sekcja 4 i 5 w następującym dokumencie: http://valis.cs.uiuc.edu/~sariel/papers/08/expand_cover/expand_cover.pdf . Jestem pewien, że istnieją inne przykłady - to tylko dokumenty, nad którymi pracowałem i tacy pamiętają, że używają takiej argumentacji.

$\Re^5$ $\Re^5$ $\Omega(n^5)$

— Sariel Har-Peled
źródło