Rechenkomplexität des 3-Partitionsproblems mit unterschiedlichen Zahlen

Diese Frage bezieht sich auf eine Antwort, die ich als Antwort auf eine andere Frage gepostet habe.

Das 3-Partitionsproblem ist das folgende Problem:
Instanz : Positive ganze Zahlen a ₁ ,…, a _n , wobei n = 3 m und die Summe der n ganzen Zahlen gleich mB ist, so dass jedes a _i B / 4 <a _i erfüllt <B / 2.
Frage : Können die ganzen Zahlen a ₁ ,…, a _n in m Multisätze unterteilt werden, so dass die Summe jedes Multisatzes gleich B ist?

Es ist bekannt, dass das 3-Partitions-Problem in dem starken Sinne NP-vollständig ist, dass es NP-vollständig bleibt, auch wenn die Zahlen in der Eingabe unär sind. Siehe Garey und Johnson für einen Beweis.

Fragen : Bleibt das 3-Partitions-Problem NP-vollständig, wenn die Zahlen a ₁ ,…, a _n alle verschieden sind? Bleibt es im starken Sinne NP-vollständig?

(Mein Gefühl ist, dass die Antworten auf beide Fragen wahrscheinlich Ja sind, weil ich keinen Grund sehe, warum das Problem einfacher werden sollte, wenn alle Zahlen unterschiedlich sind.)

Es scheint nicht, dass der Beweis in Garey und Johnson die NP-Vollständigkeit dieser eingeschränkten Version belegt.

In der Antwort auf die andere Frage oben habe ich den Beweis erbracht, dass das 6-Partitions-Problem (analog definiert) mit unterschiedlichen Zahlen im engeren Sinne NP-vollständig ist.

cc.complexity-theory np-hardness Tsuyoshi Ito
quelle

Ich denke, das ist ein wichtiges Problem. In der Literatur habe ich mehrere Veröffentlichungen gefunden, die besagen oder annehmen, dass die gesetzte Version schwierig ist, ohne eine bessere Rechtfertigung als ein Zitat zur Multiset-Version in Garey und Johnson, und die diese Annahme in einem Anspruch auf NP-Vollständigkeit für ein anderes Problem verwenden .

David Eppstein

Antworten:

In [1, Korollar 7] wird bewiesen, dass die 3-Partition stark NP-hart ist, wenn die ganzen Zahlen alle verschieden sind. Die Grenzen werden in [1] nicht auferlegt, dies sollte jedoch keinen Unterschied machen. $a_1, \ldots, a_n$ $B/4 < a_i < B/2$

[1]: Heather Hulett, Gerhard J. Woeginger, Todd G. Will: Multigraph-Realisierungen von Gradfolgen: Maximierung ist einfach, Minimierung ist schwer. Oper. Res. Lette. 36 (5): 594 & ndash; 596 (2008). DOI

Serge Gaspers
quelle

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

$B/4 < a_i < B/2$

a_{i}

$a_i$

In der Tat ist es unkompliziert, auch diese Grenzen aufzuerlegen.

Serge Gaspers

Danke, es beantwortet meine Frage vollständig. Es ist zu beachten, dass das Problem der teilweisen Vervollständigung des lateinischen Quadrats leicht als Spezialfall der dreidimensionalen Übereinstimmung formuliert werden kann. Es ist mir nicht in den Sinn gekommen, 3DM durch PLSC zu ersetzen, aber nachdem ich den Beweis gesehen habe, scheint der Ansatz ganz natürlich zu sein.

Tsuyoshi Ito