Twardość podtytuły Zestawu okładki

10

Jak trudny jest problem Ustaw okładkę, jeśli liczba elementów jest ograniczona przez jakąś funkcję (np. ), gdzie jest rozmiarem wystąpienia problemu. Formalnie, $\log n$ $n$

Niech i gdzie i . Jak trudno jest rozwiązać następujący problem $\mathcal{U}=\{e_1, \cdots, e_m\}$ $\mathcal{F} = \{S_1, \cdots, S_n\}$ $S_i \subseteq \mathcal{U}$ $m = O(\log n)$

\begin{aligned} SET-COVER' = {< U, F, k >: & there exists at most k subsets \\ S_{i_{1}}, \dots, S_{i_{k}} \in F that cover U} . \end{aligned}

$\begin{align*} \text{SET-COVER'}=\{<\mathcal{U}, \mathcal{F}, k>: &\text{ there exists at most $k$ subsets }\\ &\text{ $S_{i_1}, \cdots, S_{i_k}\in \mathcal{F}$ that cover $\mathcal{U}$} \}. \end{align*}$

Co jeśli ? $m=O(\sqrt{n})$

Każdy wynik oparty na dobrze znanych przypuszczeniach (np. Unique Games, ETH) jest dobry.

Edycja 1: Motywacją tego problemu jest ustalenie, kiedy problem staje się trudniejszy, gdy rośnie . Najwyraźniej problemem jest P, jeśli i NP-trudny, jeśli . Jaki jest próg twardości NP problemu? $m$ $m=O(1)$ $m=O(n)$

Edycja 2: Istnieje trywialne algorytm uzna, że w czasie (który wylicza wszystkie podzbiory o rozmiarze o ). Dlatego problemem nie jest NP-trudny, jeśli ponieważ ETH sugeruje, że nie ma algorytmu w czasie dla żadnego NP-twardego problem (gdzie jest wielkością problemu NP-trudnego). $O(n^{m})$ $m$ $\mathcal{F}$ $m=O(\log{n})$ $O(2^{n^{o(1)}})$ $n$

np-hardness set-cover exp-time-algorithms

— użytkownik1297
źródło

2

Istnieje lepszy algorytm decydujący o problemie w czasie

(a dokładniej liczba Bell dla

): dla każdej partycji elementów na podzbiory sprawdź, czy istnieje zbiór wejściowy obejmujący każdy podzbiór. Tak więc dla

problem można rozwiązać w czasie wielomianowym. To jednak nie do końca odpowiada na twoje pytanie dotyczące

.

m^{O (m)}

$m^{O(m)}$

m

$m$

m = O (\log n / \log \log n)

$m=O(\log n/\log\log n)$

m = O (\log n)

$m=O(\log n)$

— David Eppstein,

11

Gdy , możesz użyć programowania dynamicznego, aby znaleźć optymalny czas wielomianowy. Tabela zawiera logiczny wartościach komórek każdego i , wskazujący, czy istnieje zestawy, które obejmują elementy w . $m = O(\log n)$ $T_{\ell,X}$ $\ell \in \{0,\ldots,k\}$ $X \subseteq \mathcal{U}$ $\ell$ $X$

Gdy , powiedz $m = O(\sqrt{n})$ , problem pozostaje trudny do rozwiązania. Biorąc pod uwagę instancję SET-COVER, dodajnowe elementyoraznowe zestawy, składające się z niepustych podzbiorów nowych elementów, w tym(gdyjest wystarczająco duży,). Zwiększ także $m \leq C\sqrt{n}$ $m$ $x_1,\ldots,x_m$ $(2C^{-1}m)^2$ $\{x_1,\ldots,x_m\}$ $m$ $(2C^{-1}m)^2 < 2^m$ $k$ po jednym. Nowe jest i . $m,n$ $m' = 2m$ $n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$

— Yuval Filmus
źródło

Mówiąc bardziej ogólnie, przypadek

jest trudny NP, a przypadek

nie jest trudny NP przy założeniu ETH, ponieważ istnieje algorytm

.

m = n^{O (1)}

$m = n^{O(1)}$

m = n^{o (1)}

$m = n^{o(1)}$

p o l y (n, 2^{m})

$\mathrm{poly}(n,2^m)$

— Yuval Filmus,

11

Przypadek jest w czasie jak zauważył Yuval, ale należy również pamiętać, że dla problem można rozwiązać w czasie (czas wielomianowy) o Wyczerpujące wyszukiwanie. Zakładając hipotezę silnego czasu wykładniczego (że CNF-SAT w formułach z zmiennymi i klauzulami wymaga co najmniej $m = c \log n$ $n^{O(c)}$ $k = O(1)$ $O(n^k \cdot m)$ $N$ $O(N)$ $2^{N-o(N)}$ czas), te dwie granice czasowe są „granicą” tego, czego możemy się spodziewać w czasie wielomianowym, w następującym znaczeniu.

W moim artykule SODA'10 z Mihai Patrascu badamy zasadniczo izomorficzny problem znalezienia dominującego zestawu wielkości na dowolnym wykresie węzłowym, pokazując, że jeśli zbiór dominujący można rozwiązać w czasie dla pewnego i , wówczas istnieje algorytm czasowy dla CNF-SAT dla zmiennych i $k$ $n$ $k$ $n^{k-\varepsilon}$ $k \geq 2$ $\varepsilon > 0$ $2^{N(1-\varepsilon/2)}poly(M)$ $N$ $M$ klauzule

Zwracając uwagę na zależność między dzielnicach wierzchołków w zbiór dominujący instancji oraz zestawów w zbiorze przykład pokrywy i kontroli stopnia redukcji, można zauważyć, że ta redukcja też pokazy rozwiązywania -Set przykryć zestawów nad wszechświatem rozmiar w implikuje algorytm CNF-SAT dla formuł CNF z klauzulami i zmiennymi działającymi w $k$ $n$ $m$ $n^{k-\varepsilon}\cdot f(m)$ $M$ $N$ $2^{N(1-\varepsilon/2)}\cdot f(M)$ czas. Do celów obalenia silnego ETH wystarczy rozwiązać CNF-SAT w przypadku, gdy . Stąd algorytm dla twojego problemu działającego w czasie dla pewnej nieograniczonej funkcji dałby zaskakujący nowy algorytm SAT. $M = O(N)$ $n^{k-\varepsilon}\cdot 2^{m/\alpha(m)}$ $\alpha(m)$

— Ryan Williams
źródło