Kekerasan sebuah subcase dari Set Cover

Seberapa sulit masalah Set Cover jika jumlah elemen dibatasi oleh beberapa fungsi (misalnya, $\log n$ ) di mana $n$ adalah ukuran instance masalah. Secara formal,

Misalkan $\mathcal{U}=\{e_1, \cdots, e_m\}$ dan $\mathcal{F} = \{S_1, \cdots, S_n\}$ mana $S_i \subseteq \mathcal{U}$ dan $m = O(\log n)$ . Seberapa sulit untuk memutuskan masalah berikut ini

Bagaimana jika ?$m=O(\sqrt{n})$

Hasil apa pun berdasarkan dugaan terkenal (misalnya, Game Unik, ETH) adalah baik.

Sunting 1: Motivasi untuk masalah ini adalah mencari tahu kapan masalahnya menjadi semakin sulit ketika meningkat. Jelas, masalahnya ada di P jika m = O ( 1 ) dan NP-hard jika m = O ( n ) . Berapa ambang untuk kekerasan NP dari masalah?$m$$m=O(1)$$m=O(n)$

Sunting 2: Ada algoritma sepele untuk memutuskannya dalam waktu (yang menyebutkan semua himpunan bagian ukuran m dari F ). Oleh karena itu, masalahnya bukan NP-keras jika m = O ( log n ) karena ETH menyiratkan bahwa tidak ada algoritma dalam waktu O ( 2 n o ( 1 ) ) untuk masalah NP-hard (di mana n adalah ukuran dari Masalah NP-keras).$O(n^{m})$$m$$\mathcal{F}$$m=O(\log{n})$$O(2^{n^{o(1)}})$$n$

Ketika , Anda dapat menggunakan pemrograman dinamis untuk menemukan yang optimal dalam waktu polinomial. Tabel berisi sel Boolean bernilai T ℓ , X untuk setiap ℓ ∈ { 0 , ... , k } dan X ⊆ U , menunjukkan apakah ada ℓ set yang meliputi unsur-unsur di X .$m = O(\log n)$$T_{\ell,X}$$\ell \in \{0,\ldots,k\}$$X \subseteq \mathcal{U}$$\ell$$X$

Ketika , misalkanm≤C$m = O(\sqrt{n})$ , masalahnya tetap NP-keras. Diberikan instance SET-COVER, tambahkanmelemen barux1,…,xmdan(2C - 1 m)2set baru, yang terdiri dari himpunan bagian non-kosong dari elemen baru, termasuk{x1,...,xm}(bilamcukup besar,(2C - 1 m)2<2m). Juga tingkatkan$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$dengan satu. baru , n adalah m ′ = 2 m dan n ′ = n + ( 2 C - 1 m ) 2 ≥ ( C - 1 m ′ ) 2 .$m,n$$m' = 2m$$n' = n + (2C^{-1}m)^2 \geq (C^{-1}m')^2$

Kasus dalam waktu n O ( c ) seperti dicatat oleh Yuval, tetapi juga catatan untuk k = O ( 1 ) Anda dapat menyelesaikan masalah dalam waktu O ( n k ⋅ m ) (waktu polinomial) oleh pencarian lengkap. Dengan asumsi Hipotesis Waktu Eksponensial Kuat (bahwa CNF-SAT pada rumus dengan variabel N dan klausa O ( N ) membutuhkan setidaknya 2 N - o ( N $m = c \log n$$n^{O(c)}$$k = O(1)$$O(n^k \cdot m)$$N$$O(N)$$2^{N-o(N)}$waktu), dua batas waktu ini adalah "batas" dari apa yang dapat kita harapkan dalam waktu polinomial, dalam pengertian berikut.

Dalam makalah SODA'10 saya dengan Mihai Patrascu kami mempelajari masalah dasarnya isomorfik menemukan seperangkat mendominasi ukuran dalam grafik n -node sewenang-wenang , menunjukkan bahwa jika set k- dominasi dapat diselesaikan dalam waktu n k - ε untuk beberapa k ≥ 2 dan ε > 0 , maka ada algoritma waktu 2 N ( 1 - ε / 2 ) p o l y ( M ) untuk CNF-SAT pada variabel N dan $k$$n$$k$$n^{k-\varepsilon}$$k \geq 2$$\varepsilon > 0$$2^{N(1-\varepsilon/2)}poly(M)$$N$$M$ klausa.

Memperhatikan hubungan antara lingkungan simpul dalam satu set contoh mendominasi dan set dalam cover contoh set, dan memeriksa pengurangan, Anda akan menemukan bahwa pengurangan ini juga menunjukkan pemecahan -Mengatur Tutup dengan n set atas alam semesta dari ukuran m di n k - ε ⋅ f ( m ) waktu menyiratkan algoritma CNF-SAT untuk rumus CNF dengan klausa M dan variabel N yang berjalan dalam 2 N ( 1 - ε / 2 ) ⋅ f ( M $k$$n$$m$$n^{k-\varepsilon}\cdot f(m)$$M$$N$$2^{N(1-\varepsilon/2)}\cdot f(M)$waktu. Untuk tujuan menyangkal Strong ETH, cukup untuk menyelesaikan CNF-SAT dalam kasus di mana . Oleh karena itu suatu algoritma untuk masalah Anda yang berjalan dalam waktu n k - ε ⋅ 2 m / α ( m ) untuk beberapa fungsi tidak terikat α ( m ) akan menghasilkan algoritma SAT baru yang mengejutkan.$M = O(N)$$n^{k-\varepsilon}\cdot 2^{m/\alpha(m)}$$\alpha(m)$