Złożoność obliczeniowa problemu z 3 partycjami z różnymi liczbami

23

To pytanie jest związane z odpowiedzią, którą opublikowałem w odpowiedzi na inne pytanie.

Problemem z 3 partycjami jest następujący problem:
Instancja : dodatnie liczby całkowite a 1 ,…, a n , gdzie n = 3m, a suma n liczb całkowitych jest równa mB, tak że każda a i spełnia B / 4 <a i <B / 2.
Pytanie : Czy liczby całkowite a 1 ,… n można podzielić na m multiset, aby suma każdego multisetu była równa B?

Powszechnie wiadomo, że problem z 3 partycjami jest NP-zupełny w silnym sensie, że pozostaje NP-zupełny, nawet jeśli liczby na wejściu podano jednostronnie. Zobacz dowód Gareya i Johnsona .

Pytania : Czy problem z 3 partycjami pozostaje NP-zupełny, jeśli liczby a 1 ,…, a n są różne? Czy w pełnym tego słowa znaczeniu pozostaje on NP-zupełny?

(Mam wrażenie, że odpowiedzi na oba pytania są prawdopodobnie tak, ponieważ nie widzę żadnego powodu, dla którego problem powinien stać się łatwiejszy, jeśli wszystkie liczby są różne).

Nie wydaje się, aby dowód Garey and Johnson wykazał kompletność NP tej ograniczonej wersji.

W odpowiedzi na inne powyższe pytanie podałem dowód, że problem 6-partycjonowania (zdefiniowany analogicznie) z różnymi liczbami jest NP-zupełny w silnym znaczeniu.

Tsuyoshi Ito
źródło
2
Myślę, że to ważny problem; Znalazłem kilka artykułów w literaturze, które stwierdzają lub zakładają, że ustalona wersja jest trudna, nie ma lepszego uzasadnienia niż cytowanie wersji wielosektowej w Garey i Johnson, i które wykorzystują to założenie w twierdzeniu o kompletności NP dla innego problemu .
David Eppstein,

Odpowiedzi:

19

Udowodniono w [1, następstwie 7], że 3-partycja jest silnie NP-trudna, gdy wszystkie liczby całkowite są różne. Granice nie są narzucone w [1], ale to nie powinno mieć znaczenia.a1,,anB/4<ai<B/2

[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Multigraficzne realizacje sekwencji stopni: Maksymalizacja jest łatwa, minimalizacja jest trudna. Oper. Res. Łotysz. 36 (5): 594–596 (2008). DOI

Serge Gaspers
źródło
5
Nałożenie granic można łatwo zrobić, dodając tę ​​samą dużą liczbę do wszystkich . B/4<ai<B/2ai
David Eppstein
1
Rzeczywiście, narzucenie tych granic jest również proste.
Serge Gaspers
2
Dzięki, to kompletnie odpowiada na moje pytanie. Należy zauważyć, że problem częściowego uzupełnienia łacińskiego kwadratu można łatwo sformułować jako specjalny przypadek dopasowania trójwymiarowego. Nie przyszło mi do głowy, aby zastąpić 3DM przez PLSC, ale po zobaczeniu dowodu podejście wydaje się całkiem naturalne.
Tsuyoshi Ito