Cette question est liée à une réponse que j'ai postée en réponse à une autre question.
Le problème des 3 partitions est le problème suivant:
Instance : entiers positifs a 1 ,…, a n , où n = 3 m et la somme des n entiers est égale à mB, de sorte que chacun a i satisfait B / 4 <a i <B / 2.
Question : Les entiers a 1 ,…, a n peuvent-ils être partitionnés en m multisets de sorte que la somme de chaque multiset soit égale à B?
Il est bien connu que le problème des 3 partitions est NP-complet dans le sens fort où il reste NP-complet même si les nombres en entrée sont donnés en unaire. Voir Garey et Johnson pour une preuve.
Questions : Le problème des 3 partitions reste-t-il NP-complet si les nombres a 1 ,…, a n sont tous distincts? Reste-t-elle NP-complète au sens fort?
(Mon sentiment est que les réponses aux deux questions sont probablement oui parce que je ne vois aucune raison pour laquelle le problème devrait devenir plus facile si tous les nombres sont distincts.)
Il ne semble pas que la preuve dans Garey et Johnson établit la complétude NP de cette version restreinte.
Dans la réponse à l'autre question liée ci-dessus, j'ai donné la preuve que le problème des 6 partitions (défini de façon analogue) avec des nombres distincts est NP-complet au sens fort.
la source
Réponses:
[1]: Heather Hulett, Todd G. Will, Gerhard J. Woeginger: Réalisations multigraphiques de séquences de degrés: la maximisation est facile, la minimisation est difficile. Oper. Res. Lett. 36 (5): 594-596 (2008). EST CE QUE JE
la source