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

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 .k k S A T n m 2 ( 1 - ε ) n p o l y $\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ż .F T P ≠ W [ 1 $P \neq NP$$FTP\neq W[1]$

Cztery inne ważne przypuszczenia:

1. 3SUM Hipoteza: 3SUM na liczb całkowitych wymaga czas{ - n 3 , … , n 3 } n 2 - o ( 1 $n$$\{-n^3,…,n^3\}$$n^{2-o(1)}$

2. Hipoteza OV: Wektory ortogonalne na wektorach wymagają czasu .n 2 - o ( 1 $n$$n^{2-o(1)}$

3. 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)}$

4. 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

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

NSETH: Dla każdego istnieje k takie, że k -DNF-TAUT nie może być rozwiązany w niedeterministycznym czasie 2 ( 1 - ϵ ) n .$\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 k takie, że k -DNF-TAUT nie może zostać rozpoznany przez niedeterministyczne rodziny obwodów o rozmiarze 2 ( 1 - ϵ ) n .$\epsilon >0$$k$$k$$2^{(1-\epsilon)n}$

Innym interesującym przypuszczeniem jest twardość kliki dla ustalonego k (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ą.

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 n O ( K ) czas → N L ⊊ $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