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.
źródło
Odpowiedzi:
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.za1, … , An B / 4 < aja< 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
źródło