Jakie są relacje między tymi hipotezami w teorii drobnoziarnistej złożoności?

23

Teoria złożoności, poprzez takie koncepcje jak kompletność NP, rozróżnia problemy obliczeniowe, które mają względnie skuteczne rozwiązania, i te, które są trudne do rozwiązania. Złożoność „drobnoziarnista” ma na celu dopracowanie tego jakościowego rozróżnienia w ilościowy przewodnik co do dokładnego czasu potrzebnego na rozwiązanie problemów. Więcej informacji można znaleźć tutaj: http://simons.berkeley.edu/programs/complexity2015

Oto kilka ważnych hipotez:

ETH: $3$ - $SAT$ wymaga czasu dla niektórych . $2^{\delta n}$ $\delta > 0$

SETH: dla każdego istnieje takie, że - na zmiennych, klauzul nie można rozwiązać w czasie . $\varepsilon > 0$ $k$ $k$ $SAT$ $n$ $m$ $2^{(1-\varepsilon)n}~poly~m$

Wiadomo, że SETH jest silniejszy niż ETH i oba są silniejsze niż , i oba silniejsze niż . $P \neq NP$ $FTP\neq W[1]$

Cztery inne ważne przypuszczenia:

3SUM Hipoteza: 3SUM na liczb całkowitych wymaga czas $n$ $\{-n^3,…,n^3\}$ $n^{2-o(1)}$
Hipoteza OV: Wektory ortogonalne na wektorach wymagają czasu . $n$ $n^{2-o(1)}$
Hipoteza APSP: najkrótsza ścieżka wszystkich par w węzłach i wagach bitów wymaga czasu . $n$ $O(\log n)$ $n^{3-o(1)}$
Hipoteza BMM: Każdy algorytm „kombinatoryczny” do mnożenia macierzy boolowskich wymaga czasu . $n^{3-o(1)}$

Wiadomo, że SETH zakłada hipotezę OV (Ryan Willams, 2004). Oprócz dowodu Ryana, że SETH hipotezę OV, nie ma innych znanych redukcji odnoszących się do przypuszczeń. $\implies$

Moje pytanie: Czy znasz inne powiązane hipotezy lub przypuszczenia w tej dziedzinie? Jakie są między nimi relacje?

Podziękowania: wymienione wyniki pochodzą ze slajdów Virginii Vassilevska Williams, dała mi również częściowe odpowiedzi na to pytanie.

Link do slajdów: http://theory.stanford.edu/~virgi/overview.pdf

— Rupei Xu
źródło

Cześć Rupei, Pracowałem nad różnymi problemami związanymi z osiągalnościami i ograniczeniami grafów, które są związane z bardzo ładną listą problemów o złożoności drobnoziarnistej, o której wspomniałeś. Jeśli jesteś w ogóle zainteresowany, napisz do mnie e-maila, abyśmy mogli kiedyś porozmawiać. Cieszę się, że inni użytkownicy są zainteresowani drobnoziarnistą złożonością wymiany stosów. :)

— Michael Wehar,

3

Trywialna redukcja: „kombinatoryczny” podjednostkowy APSP implikuje „kombinatoryczny” podklubiczny BMM. W przypadku 3SUM patrz relację między pokrewnymi problemami na stronie 14 tego slajdu cs.uwaterloo.ca/~tmchan/talks/bsg_stoc_talk.pdf . BMM, patrz sekcja G tej teorii papieru . Stanford.edu/~virgi/tria-mmult-conf.pdf . W przypadku APSP istnieje wiele prac Virginii wykazujących podjednostkę podrzędną.

— Thatchaphol,

1

@Thatchaphol, dziękuję za miłe udostępnianie!

— Rupei Xu,

15

Jest to najnowszy artykuł przedstawiający niedeterministyczną hipotezę silnego czasu wykładniczego (NSETH), która jest rozszerzeniem SETH.

NSETH: Dla każdego istnieje takie, że -DNF-TAUT nie może być rozwiązany w niedeterministycznym czasie . $\epsilon >0$ $k$ $k$ $2^{(1-\epsilon)n}$

NSETH oznacza SETH. Jeśli NSETH jest prawdą, wówczas niektóre problemy nie mają dolnych granic SETH (ponieważ mają algorytmy niedeterministyczne szybciej niż algorytmy deterministyczne).

W pracy przedstawiono także niejednolitą niedeterministyczną hipotezę silnego czasu wykładniczego (NUNSETH), hipotezę silniejszą niż NSETH i SETH.

NUNSETH: Dla każdego istnieje takie, że -DNF-TAUT nie może zostać rozpoznany przez niedeterministyczne rodziny obwodów o rozmiarze . $\epsilon >0$ $k$ $k$ $2^{(1-\epsilon)n}$

— Rosetta
źródło

1

Dziękujemy za pionierską pracę! Ryan Williams uważa, że SETH jest fałszywe. Czy uważasz, że NSETH jest prawdą?

— Rupei Xu,

2

W tym dokumencie zauważono, że Ryan faktycznie wykazał, że MA wersja SETH jest fałszywa, co wydaje się sugerować, że NSETH jest mało prawdopodobne. Niemniej jednak w pewnym sensie chodzi o to, że aby pokazać powiązania między niektórymi z tych innych przypuszczeń, najpierw trzeba by poczynić postępy w obalaniu NSETH.

— palindrom

8

Innym interesującym przypuszczeniem jest twardość kliki dla ustalonego (patrz tutaj ). $k$ $k$

Nie jest to dokładnie ten rodzaj relacji, którego szukasz, ale był interesujący artykuł FOCS pokazujący, że naturalny problem zwany „dopasowywaniem trójkątów” jest trudny w przypadku jakichkolwiek przypuszczeń w SETH, 3SUM lub APSP (patrz tutaj ). Obecnie nie wiadomo, czy którakolwiek z tych trzech domysłów implikuje się w jakikolwiek interesujący sposób - jest to jedno z głównych otwartych pytań o złożoność drobnoziarnistą.

— GMB
źródło

1

Dziękuję Greg! Moją pierwotną motywacją do opublikowania tego pytania tutaj jest zebranie wszystkich istniejących wyników w tym obszarze, takich jak dobre zbiory w Biuletynie sparametryzowanej

— Rupei Xu,

-clique związek wydaje się być uszkodzony. Pomyślałem, że dam ci znać. :)

k

$k$

— Michael Wehar,

1

stosunkowo niedawne wyniki Backursa, Indyk zaakceptował na STOC 2015, że obliczanie odległości edycji w czasie → SETH fałszywe powiązanie w zgrabny / silny sposób z nowym, rozwijającym się programem / paradygmatem „drobnoziarnistej złożoności”. są ściśle powiązane / oparte na wynikach Williamsa, których domysł SETH → Wektory ortogonalne. (nawet w mediach głównego nurtu, Boston Globe). $O(n^{2-\epsilon})$

Edycja odległości nie może być obliczona w silnie subkwadratycznym czasie (chyba że SETH ma wartość false) / Backurs, Indyk
Nowa mapa śledzi granice obliczeń / Pavlus, magazyn Quanta
Przez 40 lat informatycy szukali rozwiązania, które nie istnieje / Boston Globe
Puzzling Evidence / RJLipton blog

pozornie bardzo podobny wynik spowodowany przez Wehara uważa problem „pustki przecięcia 2 DFA” i stwierdza, że czas → SETH jest fałszywy. $O(n^{2-\epsilon})$

Decydowanie o pustce przecięcia języków regularnych w czasie subkwadratowym / cstheory SE

Wehar ma inne wyniki, które wydają się również mieszczą się ogólne złącze złożoność „drobnoziarnisty”, to samo DFA przecięcia pustki czas → $k$ $n^{o(k)}$ $NL \subsetneq P$

Wyniki twardości dla skrzyżowania Brak pustki / Wehar

wzdłuż tych linii warto również wspomnieć, że istnieje znany znaczący związek między konstrukcjami DFA i obliczeniami odległości Levenshteina, np. w tym artykule

Szybka korekta łańcucha za pomocą automatów Levenshtein / Shulz, Mihov

— vzn
źródło

1

Dodano kilka drobnych poprawek do Twojego posta VZN. Miło z twojej strony, że o mnie wspomniałeś. Jestem bardzo pasjonatem problemu przecięcia DFA i mam nadzieję, że w przyszłości będę miał więcej rzeczy do podzielenia się. :)

— Michael Wehar,