Steckenpuzzle

18

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,,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

Jagadisch
quelle
1
Die Problemformulierung in dem Link, den Sie angegeben haben, hat die folgende zusätzliche Anforderung, mit der das Problem sinnvoller zu sein scheint: "Keiner der Sticks ist kürzer als ." n
Jukka Suomela
Es ist ein ungelöstes Problem festzustellen, ob dies immer möglich ist.
Emil
@Emil: Hast du eine Referenz? Gibt es etwas Neues als die alte (1995) Diskussion im OP?
Jukka Suomela
@Jukka Mein Fehler. Ich habe vergessen, diesen Punkt zu erwähnen, da ich den Eindruck hatte, dass sich das Problem mit dieser Einschränkung nicht wesentlich ändern wird. Wie auch immer, ich bin glücklich, seit Tsuyoshi eine interessante Frage beantwortet hat.
Jagadish
Dies ist ein ziemlich ordentliches Problem, aber der Titel ist irreführend. Es deutet darauf hin, dass dies ein komplexitätstheoretisches Problem ist, obwohl es sich um ein cooles Algorithmus-Rätsel handelt, genau wie das Problem des Nichtmischens. Vielleicht solltest du den Titel umformulieren.
Suresh Venkat

Antworten:

16

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 1 ,…, 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 1 ,…, 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 1 , ..., 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 1 ,…, a n besteht . Sei m = n / 3 und B = (a 1 +… + 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 1 ,…, 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

Tsuyoshi Ito
quelle
3
Ich weiß nicht, ob das 3-Partitions-Problem NP-vollständig bleibt oder nicht, ob die Nummern unterschiedlich sind, und ich frage danach
Tsuyoshi Ito
Serge Gaspers sagte mir, dass dies der Fall ist (danke!). Ich habe den Beweis damit vereinfacht.
Tsuyoshi Ito