Zmniejszenie problemu z 3 partycjami do problemu zrównoważonej partycji

Problem 3 partycji zapytuje, czy zestaw liczb może być podzielona na n zestawy trzech liczb całkowitych takim, że każdy zestaw razem daje z danym całkowitą B . Problem zrównoważonej partycji pyta, czy 2 n liczb całkowitych można podzielić na dwa równe zestawy liczności, tak aby oba zestawy miały tę samą sumę. Oba problemy są znane jako NP-zupełne. Jednak 3-partycja jest silnie NP-kompletna. W literaturze nie widziałem żadnej redukcji z 3-partycji do zrównoważonej partycji.$3n$$n$$B$$2n$

Szukam (prostej) redukcji z 3-partycji do problemu zrównoważonej partycji.

W literaturze są tysiące problemów z NP-zupełnością, a większość par nie ma wyraźnych redukcji. Ponieważ składają się wielokrotne redukcje wielomianowe w czasie wielomianowym, wystarczy, aby naukowcy przestali, gdy wykres opublikowanych redukcji jest silnie powiązany, dzięki czemu badania kompletności NP są znacznie bardziej skalowalne.

Chociaż naprawdę nie rozumiem sensu, będę cię żartować, podając dość prostą redukcję z 3-PARTITION do BALANCED PARTITION, z kilkoma wskazówkami na temat tego, jak idzie dowód poprawności.

Niech wkładem redukcji będzie , instancja 3-PARTITION. Należy sprawdzić, czy Ď i ∈ [ 3 N ] x ı = n B . Niech β będzie dużą liczbą, która zostanie wybrana później. Dla każdego i ∈ [ 3 n ] i każdego j ∈ [ n ] wypisz dwie liczby x i β j + β n $x_1, \ldots, x_{3n}, B \in \mathbb Z$$\sum_{i\in[3n]} x_i = nB$$\beta$$i \in [3n]$$j \in [n]$ Intuicyjnie pierwsza liczba oznacza, że x i jest przypisana do 3-partycji j , a druga liczba oznacza odwrotnie. Termin x i β j służy do śledzenia sumy 3-partycji j . Termin β n + j służy do śledzenia liczności 3-częściowej j . Termin β 2 n + i służy do zapewnienia, że ​​każdemu x i przypisano dokładnie jeden raz. Β

$$x_i \beta^j + \beta^{n+j} + \beta^{2n+i} + \beta^{(i+4)n+j}\\ \beta^{(i+4)n+j}.$$ $x_i$$j$$x_i \beta^j$$j$$\beta^{n+j}$$j$$\beta^{2n+i}$$x_i$ Termin n + j służy do wymuszenia tych liczb w różnych zrównoważonych partycjach.$\beta^{(i+4)n+j}$

Wyjmij dwie kolejne liczby Pierwsza liczba określa zrównoważoną partycję jako „prawda”, a druga jako „fałsz”. Termin 1 służy do wymuszenia tych liczb w różnych zrównoważonych partycjach. Pozostałe warunki nadrobić różnicę między sumą 3-partycji a sumą jego dopełnieniem i wielkości 3-partycji i wielkości jego dopełnieniem i ile razy x i jest przypisany.

$$1 + \sum_{j\in[n]} \Bigl((n-2)B\beta^j + (3n-6)\beta^{n+j}\Bigr) + \sum_{i\in[3n]} (n-2)\beta^{2n+i}\\ 1.$$ $1$$x_i$

należy wybrać wystarczająco duży, aby zapobiec wystąpieniu „przepełnienia”.$\beta$

Ten artykuł, Fast Balanced Partitioning jest trudny nawet na siatkach i drzewach , autorstwa Andreasa Emila Feldmanna zawiera to, czego chcesz! Powodzenia!

$k$