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

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 ₁ ,…, 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 ₁ ,… _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 ₁ ,…, 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.

cc.complexity-theory np-hardness

— Tsuyoshi Ito
źródło

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,

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. $a_1, \ldots, a_n$ $B/4 < a_i < 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

Nałożenie granic można łatwo zrobić, dodając tę samą dużą liczbę do wszystkich .

B / 4 < a_{i} < B / 2

$B/4 < a_i < B/2$

a_{i}

$a_i$

— David Eppstein

Rzeczywiście, narzucenie tych granic jest również proste.

— Serge Gaspers

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