Układanka do cięcia pałeczek

18

Problem: Dostajemy zestaw drążków o długości całkowitej. Całkowita suma ich długości wynosi n (n + 1) / 2.

Czy możemy je rozbić, aby uzyskać kije wielkości czasie wielomianowym? 1,2),,n

Co zaskakujące, jedynym odniesieniem do tego problemu jest starożytna dyskusja:

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

Co jeszcze wiadomo na temat problemu? Czy możemy udowodnić, że problemem jest „otchłań”?

Aktualizacja: Problem drążków tnących wiąże się z tym, że każdy drążek ma co najmniej jednostek długości. (Zobacz komentarze i odpowiedź Tsuyoshi dla przypadku nieograniczonego).n

Jagadish
źródło
1
Sformułowanie problemu w podanym linku ma następujące dodatkowe wymaganie, z którym problem wydaje się bardziej sensowny: „Żaden z drążków nie jest krótszy niż ”. n
Jukka Suomela,
Problemem jest ustalenie, czy zawsze jest to możliwe.
Emil
@Emil: Czy masz referencję? Czy jest coś nowszego niż starożytna (1995) dyskusja powiązana w PO?
Jukka Suomela,
@Jukka Mój błąd. Zapomniałem wspomnieć o tym punkcie, ponieważ miałem wrażenie, że problem nie zmieni się znacząco z tym ograniczeniem. W każdym razie jestem szczęśliwy, ponieważ odpowiedź Tsuyoshi zrodziła interesujące pytanie.
Jagadish
jest to dość fajny problem, ale tytuł wprowadza w błąd. Sugeruje to, że jest to problem teorii złożoności, kiedy tak naprawdę jest to fajna łamigłówka algorytmiczna, podobnie jak problem z tasowaniem. Może powinieneś przeredagować tytuł.
Suresh Venkat

Odpowiedzi:

16

Uwaga: Jak Jukka Suomela skomentował pytanie, strona z linkiem do pytania dotyczy innego problemu niż problem wskazany w pytaniu, ponieważ problem na stronie ma ograniczenie, że długości danych patyczków są większe lub równe n. Ta odpowiedź dotyczy problemu bez tego ograniczenia. Ponieważ komentarz Emila do pytania odnosi się do problemu z ograniczeniem, nie ma sprzeczności między jego komentarzem a następującą odpowiedzią.


Problem jest NP-zupełny, nawet jeśli liczby podano jednostronnie.

Problemem z 3 partycjami jest następujący problem:
Wystąpienie : dodatnie liczby całkowite a 1 ,…, nw jednostkowej , gdzie n = 3m, a suma n liczb całkowitych jest równa mB, tak że każda a i spełnia B / 4 < a i <B / 2.
Pytanie : Czy liczby całkowite a 1 ,… n można podzielić na m multiset, aby suma każdego multisetu była równa B?

Problem z 3 partycjami jest NP-zupełny, nawet jeśli 1 ,…, n są różne [HWW08] (dziękuję Serge Gaspers za to , że mi o tym powiedziałeś ). Możliwe jest ograniczenie tej ograniczonej wersji problemu z 3 partycjami do tego problemu w następujący sposób.

Załóżmy, że otrzymaliśmy przykład problemu z 3 partycjami składającego się z różnych dodatnich liczb całkowitych a 1 ,…, n . Niech m = n / 3 i B = (a 1 +… + a n ) / m, i niech N będzie maksimum wśród i . Rozważmy następujące wystąpienie problemu sztyftu: wystąpienie zawiera jeden kawałek o długości K dla każdego k∈ {1, ..., N} ∖ {A 1 , ..., A N }, a m pałeczki o długości B, wykorzystując fakt że każdy a i spełnia warunek i > B / 4 ≥ N / 2, łatwo jest udowodnić, że ten problem z drążkiem ma rozwiązanie, i tylko wtedy, gdy wystąpi problem z 3 partycjami.

Bibliografia

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Multigraficzne realizacje sekwencji stopni: maksymalizacja jest łatwa, minimalizacja jest trudna. Operacje Research Letters , 36 (5): 594-596, wrzesień 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004

Tsuyoshi Ito
źródło
3
Nie wiem, czy problem z 3 partycjami pozostaje NP-zupełny, czy nie, jeśli liczby są różne, i pytam o to: cstheory.stackexchange.com/questions/716/…
Tsuyoshi Ito
Serge Gaspers powiedział mi, że tak (dzięki!). Uprościłem dowód, używając go.
Tsuyoshi Ito