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ą.
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
Zauważ, że F ma taki sam rozmiar jak U , ale rozmiar C jest niepewny.
Czy ktoś może powiedzieć, czy powyższy problem dotyczy NP? (zestaw osłon? opakowanie? idealne pokrycie)
Dziękuję za Twój czas.
Odpowiedzi:
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 i|Fi|≪n=|U| (F,U,k) (F′=Fn,U′=Un,k) n , k ) (gdzie i(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|≤n≪n2=|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.ei∈Fi
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 .ϕ (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 In ϕ 3n+1 U t xi ϕ xi x¯¯¯i , a F I (na "fałsz").fi
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 , xxi ϕ {xi,x¯¯¯i,fi,t} F ϕ F t x1∧x¯¯¯2∧x3 3 , t }{x1,x¯¯¯2,x3,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 .ϕ C ∑j|Cj|=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 5ϕ C 3n+1 xi t {x¯¯¯i,t} xi 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 } .){xi,x¯¯¯i,fi,t} t {x¯¯¯i,t},{xi},{fi}
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 } .){x1,x¯¯¯2,x3,t} t {x1,t},{x¯¯¯2},{x3}
(if) Suppose there is a solution CC of size 5n+15n+1 . The solution must contain the 3n+13n+1 singleton sets, plus other sets of total size 2n2n .
Consider first the nn "variable" sets, each of the form {xi,¯xi,fi,t}{xi,x¯¯¯i,fi,t} . The set is the disjoint union of at most three sets in CC . Without loss of generality, it is the disjoint union of two singletons and a pair (otherwise, splitting sets in CC achieves this without increasing the cost). Denote the pair PiPi . The pairs PiPi and PjPj for different variables xixi and xjxj are distinct, because PiPi contains xixi , ¯xix¯¯¯i , or fifi but PjPj does not. Hence, the sum of the sizes of these pairs is 2n2n . So these pairs are the only non-singleton sets in the solution.
Next consider the "clause" sets, e.g, {xi,¯xj,xk,t}{xi,x¯¯¯j,xk,t} . Each such set must be the union of at most three sets in CC , that is, up to two singleton sets and at least one pair PiPi , PjPj , or PkPk . 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 {xi,t}{xi,t} or {¯xj,t}{x¯¯¯j,t} (a literal and tt ).
Hence, the following assignment satisfies ϕϕ : assign true to each variable xixi such that Pi={xi,t}Pi={xi,t} , assign false to each variable xixi such that Pi={¯xi,t}Pi={x¯¯¯i,t} , and assign the remaining variables arbitrarily.
Stage 2. The instance (F,U,k=3)(F,U,k=3) produced above does not satisfy the constraint ei∈Fiei∈Fi stated in the problem description. Fix that shortcoming as follows. Order the sets FiFi and elements eiei in UU so that each singleton set corresponds to its element eiei . Let mm be the number of clauses in ϕϕ , so |F|=1+4n+m|F|=1+4n+m and |U|=1+3n|U|=1+3n .
Let (F′,U′,k′=4)(F′,U′,k′=4) denote the instance obtained as follows. Let AA be a set of 2n+2m2n+2m new artificial elements, two for each non-singleton set in FF . Let U′=U∪AU′=U∪A . Let F′F′ contain the singleton sets from FF , plus, for each non-singleton set FiFi in FF , two sets Fi∪{ai,a′i}Fi∪{ai,a′i} and {ai,a′i}{ai,a′i} , where aiai and a′ia′i are two elements in AA chosen uniquely for FiFi . Now |F′|=|U′|=1+5n+2m|F′|=|U′|=1+5n+2m and (with the proper ordering of F′F′ and U′U′ ) the constraint e′i∈F′ie′i∈F′i is met for each set F′iF′i .
To finish, note that (F′,U′,k′=4)(F′,U′,k′=4) has a solution of cost |A|+5n+1|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 {ai,a′i} (one for each non-singleton Fi, 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 Fi∪{ai,a′i} and {ai,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 {ai,a′i} and the rest don't contain ai 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 {ai,a′i} sets from C′ gives a solution C for (F,U,k=3) of cost 5n+1. ⋄
źródło