Czy następujący problem NP jest trudny?

Rozważmy zbiór zbiorów F = { F 1 , F 2 , … , F n } nad zestawem podstawowym U = { e 1 , e 2 , … , e n } gdzie | F i | « N i e i ∈ F I i pozwolić K jest dodatnią liczbą całkowitą.$F=\{F_1,F_2,\dotsc,F_n\}$$U=\{e_1,e_2,\dotsc,e_n\}$$|F_i|$ $\ll$ $n$$e_i \in F_i$$k$

Celem jest, aby znaleźć inny zbiór zestawów C = { C 1 , C 2 , ... , C m } nad U takie, że każdy F i może być zapisany jako unii co najwyżej k ( k < < | C | ) wzajemnie rozłączne ustawia w C i też chcemy ∑ m 1 | C j | być minimalna (tj. łączna liczba elementów we wszystkich zestawach $C=\{C_1,C_2,\dotsc,C_m\}$$U$$F_i$$k$ $(k<<|C|)$ $C$$\sum_1^m |C_j|$$C$ powinien być jak najmniejszy).

Zauważ, że F ma taki sam rozmiar jak U , ale rozmiar C jest niepewny.$F$$U$$C$

Czy ktoś może powiedzieć, czy powyższy problem dotyczy NP? (zestaw osłon？ opakowanie？ idealne pokrycie）

Dziękuję za Twój czas.

Lemat. Problem jest trudny NP.

Szkic próbny. Nie uwzględniamy ograniczeń | F i | ≪ n = | U | w opublikowanym problemie, ponieważ dla dowolnej instancji ( F , U , k ) problemu, instancja ( F ′ = F n , U ′ = U n , k ) uzyskana przez wzięcie n niezależnych kopii ( F , U tej kopii F używa $|F_i| \ll n = |U|$$(F,U,k)$$(F'=F^n,U'=U^n,k)$$n$ , k ) (gdzie$(F,U,k)$$i$$F$$i$ tej kopii U, ponieważ jej zbiór podstawowy jest równoważny i spełnia ograniczenie (ma | F ′ i | ≤ n ≪ n 2 = | U ′ | ).$U$$|F'_i| \le n \ll n^2 = |U'|$

Dajemy redukcję z 3-SAT. Do prezentacji w pierwszym etapie redukcji pomijamy ograniczenia e i ∈ F i w opublikowanym problemie. W drugim etapie opisujemy, jak sprostać tym ograniczeniom, zachowując przy tym poprawność redukcji.$e_i \in F_i$

Pierwszy etap. Napraw dowolną formułę 3-SAT ϕ . Załóżmy WLOG, że każda klauzula ma dokładnie trzy literały (każda używa innej zmiennej). Wywołaj następujący przykład ( F , U , k ) opublikowanego problemu, przy k = 3 .$\phi$$(F,U,k)$$k=3$

Niech n będzie liczbą zmiennych w ϕ . Istnieją 3 n + 1 w elementach U : jeden element t (na "true"), a dla każdej zmiennej x I w cp trzy elementy x i , Ż x$n$$\phi$$3n+1$$U$$t$$x_i$$\phi$$x_i$$\overline x_i$ , a F I (na "fałsz").$f_i$

Dla każdego elementu U jest zestaw zawierający tylko pojedyncza że element F . Każde rozwiązanie C obejmuje zatem każdy z tych zestawów, które przyczyniają się do ich całkowitego rozmiaru 3 n $U$$F$$C$ 1 do kosztów C .$3n+1$$C$

Dodatkowo, dla każdej zmiennej x I w cp jest "zmienna" zestaw { x I , Ż x I , F I , T } w F . Dla każdego punktu w cp jest „punkt” ustawione w F składający się literałach w pkt i t . Na przykład, klauzula x 1 ∧ ¯ x 2 ∧ x 3 zwraca zbiór { x 1 , ¯ x 2 , $x_i$$\phi$$\{x_i, \overline x_i, f_i, t\}$$F$$\phi$$F$$t$$x_1\wedge \overline x_2 \wedge x_3$$\{x_1, \overline x_2, x_3, t\}$ w F .$F$

Twierdzenie 1. Redukcja jest poprawna: ϕ jest satysfakcjonująca, jeśli niektóre rozwiązanie C ma koszt ∑ j | C j | = 5 n + 1 .$\phi$$C$$\sum_j |C_j| = 5n+1$

(tylko jeśli) Załóżmy, że ϕ jest zadowalająca. Skonstruuj rozwiązanie C składające się z 3 zestawów singletonów 3 n + 1 , plus, dla każdej zmiennej x i , parę składającą się z prawdziwego literału it . (Np. { ¯ x i , t } jeśli x i jest fałszem.) Koszt C wynosi wtedy $\phi$$C$$3n+1$$x_i$$t$$\{\overline x_i, t\}$$x_i$$C$ n + 1 . $5n+1$

Każdy zestaw zmiennych { x i , ¯ x i , f i , t } jest sumą trzech zbiorów: pary składającej się z prawdziwego literału it oraz dwóch zestawów singletonów, po jednym dla każdego z pozostałych dwóch elementów. (Np. { ¯ x i , t } , { x i } , { f i } .)$\{x_i, \overline x_i, f_i, t\}$$t$$\{\overline x_i, t\}, \{x_i\}, \{f_i\}$

Każdy zestaw punkt (np { x 1 , Ż x 2 , x 3 , t } ) jest sumą trzech grup: parę składającą się z t i prawdziwego dosłownym plus dwa zestawy pojedynczych, po jednym dla każdej z dwóch literałach. (Np. { X 1 , t } , { ¯ x 2 } , { x 3 } .)$\{x_1, \overline x_2, x_3, t\}$$t$$\{x_1, t\}, \{\overline x_2\}, \{x_3\}$

(if) Suppose there is a solution $C$ of size $5n+1$. The solution must contain the $3n+1$ singleton sets, plus other sets of total size $2n$.

Consider first the $n$ "variable" sets, each of the form $\{x_i, \overline x_i, f_i, t\}$. The set is the disjoint union of at most three sets in $C$. Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in $C$ achieves this without increasing the cost). Denote the pair $P_i$. The pairs $P_i$ and $P_j$ for different variables $x_i$ and $x_j$ are distinct, because $P_i$ contains $x_i$, $\overline x_i$, or $f_i$ but $P_j$ does not. Hence, the sum of the sizes of these pairs is $2n$. So these pairs are the only non-singleton sets in the solution.

Next consider the "clause" sets, e.g, $\{x_i, \overline x_j, x_k, t\}$. Each such set must be the union of at most three sets in $C$, that is, up to two singleton sets and at least one pair $P_i$, $P_j$, or $P_k$. By inspection of the pairs and the clause set, it must be the union of two singletons and one pair, and that pair must be of the form $\{x_i, t\}$ or $\{\overline x_j, t\}$ (a literal and $t$).

Hence, the following assignment satisfies $\phi$: assign true to each variable $x_i$ such that $P_i=\{x_i, t\}$, assign false to each variable $x_i$ such that $P_i=\{\overline x_i, t\}$, and assign the remaining variables arbitrarily.

Stage 2. The instance $(F,U,k=3)$ produced above does not satisfy the constraint $e_i \in F_i$ stated in the problem description. Fix that shortcoming as follows. Order the sets $F_i$ and elements $e_i$ in $U$ so that each singleton set corresponds to its element $e_i$. Let $m$ be the number of clauses in $\phi$, so $|F|=1+4n+m$ and $|U|=1+3n$.

Let $(F', U', k'=4)$ denote the instance obtained as follows. Let $A$ be a set of $2n+2m$ new artificial elements, two for each non-singleton set in $F$. Let $U'=U\cup A$. Let $F'$ contain the singleton sets from $F$, plus, for each non-singleton set $F_i$ in $F$, two sets $F_i\cup \{a_i, a_i'\}$ and $\{a_i,a_i'\}$, where $a_i$ and $a_i'$ are two elements in $A$ chosen uniquely for $F_i$. Now $|F'|=|U'|=1+5n+2m$ and (with the proper ordering of $F'$ and $U'$) the constraint $e'_i\in F'_i$ is met for each set $F'_i$.

To finish, note that $(F',U',k'=4)$ has a solution of cost $|A|+5n+1$ iff the original instance $(F, U, k=3)$ has a solution of cost $5n+1$.

(if) Given any solution $C$ of cost $5n+1$ for $(F,U,k=3)$, adding the $n+m$ sets $\{a_i, a'_i\}$ (one for each non-singleton $F_i$, so these partition $A$) to $C$ gives a solution to $(F', U', k'=4)$ of cost $|A|+cost(C)=|A|+5n+1$.

(only if) Consider any solution $C'$ for $(F', U',k=4)$ of cost $|A|+5n+1$. Consider any pair of non-singleton sets $F_i\cup\{a_i, a_i'\}$ and $\{a_i, a_i'\}$ in $F'$. Each is the disjoint union of at most 4 sets in $C'$. By a local-exchange argument, one of these sets is $\{a_i, a_i'\}$ and the rest don't contain $a_i$ or $a_i'$ --- otherwise this property can be achieved by a local modification to the sets, without increasing the cost... (lack of detail here is why I'm calling this a proof sketch). So removing the $\{a_i, a_i'\}$ sets from $C'$ gives a solution $C$ for $(F,U,k=3)$ of cost $5n+1$. $\diamond$