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

13

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.3)nnb2)n

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

Mohammad Al-Turkistany
źródło
Chcesz więc mapowania z instancji 3-partycjonowanych instancji Balanced Partition? („meta-redukcja” w tym samym kierunku szukałaby odwzorowania w innym).
Raphael
Co to jest meta-redukcja?
Mohammad Al-Turkistany
2
Szukam redukcji Karp problemu 3 partycji do problemu partycji zrównoważonej. Mam nadzieję, że to jasne.
Mohammad Al-Turkistany
1
Jestem zadowolony ze złożonych redukcji.
Mohammad Al-Turkistany
2
ponieważ jest słabo , prawdopodobnie trzeba trick podobny do tego, o zmniejszenie 3SAT do niego, które będą korzystać z numerów z dużą ilością bitów. Zobacz na przykład Sipser. I zawsze możesz połączyć wielokrotną redukcję, aby uzyskać to, czego chcesz, zobacz to . N.P.-hzarre
Kaveh

Odpowiedzi:

1

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 +x1,,x3)n,bZja[3)n]xja=nbβja[3)n]jot[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. Β (

xjaβjot+βn+jot+β2)n+ja+β(ja+4)n+jotβ(ja+4)n+jot.
xjajotxjaβjotjotβn+jotjotβ2)n+jaxja Termin n + j służy do wymuszenia tych liczb w różnych zrównoważonych partycjach.β(ja+4)n+jot

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+jot[n]((n-2))bβjot+(3)n-6)βn+jot)+ja[3)n](n-2))β2)n+ja1.
1xja

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

Herm
źródło
2
Trudno jest śledzić / wierzyć w swoją konstrukcję bez skomplikowanych pomysłów lub dowodów. Czy możesz podać przynajmniej jedno z nich?
Raphael
0

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

k

Daniel
źródło
Ten artykuł nie ma nic wspólnego z problemem zadanym przez Mohammada. Ten dotyczy dzielenia wierzchołków wykresu w celu zminimalizowania liczby krawędzi między partycjami.
domotorp