Steckenpuzzle

Problem: Wir erhalten eine Reihe von Sticks, die alle eine ganzzahlige Länge haben. Die Gesamtsumme ihrer Längen beträgt n (n + 1) / 2.

Können wir sie in polynomielle Zeit um Stäbe der Größe zu erhalten? ${1,2,\ldots,n}$

Überraschenderweise ist der einzige Hinweis, den ich für dieses Problem finde, diese uralte Diskussion:

http://www.iwriteiam.nl/cutsticks.html

Was ist sonst noch über das Problem bekannt? Können wir beweisen, dass das Problem in der Schwebe liegt?

Update: Das Problem mit den Schneidstöcken hat die Einschränkung, dass jeder Stock mindestens Einheiten lang ist. (Siehe die Kommentare und die Antwort von Tsuyoshi für den uneingeschränkten Fall).$n$

Achtung: Da Jukka Suomela die Frage kommentierte, handelt es sich bei der mit der Frage verknüpften Seite um ein anderes Problem als das in der Frage angegebene, da das Problem auf der Seite eine Einschränkung dahingehend aufweist, dass die Länge der angegebenen Stöcke größer oder gleich ist n In dieser Antwort geht es um das Problem ohne diese Einschränkung. Da sich Emils Kommentar auf die Frage auf das Problem mit der Einschränkung bezieht , besteht kein Widerspruch zwischen seinem Kommentar und der folgenden Antwort.

Das Problem ist NP-vollständig, auch wenn die Zahlen unär sind.

Das 3-Partitions-Problem ist das folgende Problem:
Instanz : Positive ganze Zahlen a ₁ ,…, a _n in unary, wobei n = 3m und die Summe der n ganzen Zahlen gleich mB ist, so dass jedes a _i B / 4 <erfüllt a _i <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?

Das 3-Partitions-Problem ist NP-vollständig, auch wenn a ₁ , ..., a _n alle verschieden sind [HWW08] (Vielen Dank an Serge Gaspers , der mir davon erzählt hat ). Es ist möglich, diese eingeschränkte Version des 3-Partitions-Problems auf das betreffende Problem wie folgt zu reduzieren.

Angenommen, wir erhalten eine Instanz des 3-Partitions-Problems, das aus verschiedenen positiven ganzen Zahlen a ₁ ,…, a _{n besteht} . Sei m = n / 3 und B = (a ₁ +… + a _n ) / m und sei N das Maximum unter a _i . Betrachten Sie die folgende Instanz des Stick-Problems: Die Instanz besteht aus einem Stick der Länge k für jedes k∈ {1,…, N} ∖ {a ₁ ,…, a _n } und m Sticks der Länge B. Unter Verwendung der Tatsache dass jedes a _i ein _i > B / 4 ≥ N / 2 erfüllt , ist es einfach zu beweisen, dass dieses Stick-Problem nur dann eine Lösung hat, wenn die Instanz des 3-Partitions-Problems eine Lösung hat.

Verweise

[HWW08] Heather Hulett, Todd G. Will und Gerhard J. Woeginger. Multigraph-Realisierungen von Gradfolgen: Maximierung ist einfach, Minimierung ist schwierig. Operations Research Letters , 36 (5): 594–596, Sept. 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004