Complexité informatique du problème des 3 partitions avec des nombres distincts

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

cc.complexity-theory np-hardness Tsuyoshi Ito
la source

Je pense que c'est un problème important; J'ai trouvé plusieurs articles dans la littérature qui indiquent ou supposent que la version définie est difficile, sans meilleure justification qu'une citation de la version multiset dans Garey et Johnson, et qui utilisent cette hypothèse dans une revendication de complétude NP pour un autre problème .

David Eppstein

$a_1, \ldots, a_n$ $B/4 < a_i < B/2$

[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

Serge Gaspers
la source

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

$B/4 < a_i < B/2$

a_{i}

$a_i$

En effet, il est simple d'imposer également ces limites.

Serge Gaspers

Merci, cela répond complètement à ma question. Notez que le problème d'achèvement du carré latin partiel peut être facilement formulé comme un cas particulier de l'appariement en trois dimensions. Il ne m'est pas venu à l'esprit de remplacer 3DM par PLSC, mais après avoir vu la preuve, l'approche semble assez naturelle.

Tsuyoshi Ito

Complexité informatique du problème des 3 partitions avec des nombres distincts

Réponses: