Puzzle de estacas

18

Problema: Recebemos um conjunto de paus, todos com comprimentos inteiros. A soma total de seus comprimentos é n (n + 1) / 2.

Podemos separá-los para obter pedaços do tamanho em tempo polinomial? 1,2,,n

Surpreendentemente, a única referência que encontro para esse problema é essa discussão antiga:

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

O que mais se sabe sobre o problema? Podemos provar que o problema está "no limbo"?

Atualização: O problema dos bastões de corte tem a restrição de que cada bastão tenha pelo menos unidades de comprimento. (Veja os comentários e a resposta de Tsuyoshi para o caso sem restrições).n

Jagadish
fonte
1
A formulação do problema no link que você forneceu tem o seguinte requisito adicional, com o qual o problema parece fazer mais sentido: "Nenhuma das varas é menor que ". n
Jukka Suomela 28/08/10
É um problema não resolvido para determinar se isso é sempre possível.
Emil
@Emil: Você tem uma referência? Alguma coisa mais recente que a discussão antiga (1995) ligada no OP?
Jukka Suomela 28/08/10
@Jukka Meu erro. Esqueci de mencionar esse ponto, pois tinha a impressão de que o problema não mudaria significativamente com essa restrição. Enfim, estou feliz porque a resposta de Tsuyoshi gerou uma pergunta interessante.
Jagadish
esse é um problema bastante interessante, mas o título é enganoso. Isso sugere que esse é um problema da teoria da complexidade, quando na verdade é um quebra-cabeça legal de algoritmos, assim como o problema de não embaralhar. Talvez você deva reformular o título.
Suresh Venkat

Respostas:

16

Cuidado: Como Jukka Suomela comentou a questão, a página vinculada à pergunta trata de um problema diferente do problema indicado na pergunta, em que o problema na página tem uma restrição de que os comprimentos de determinados paus são maiores ou iguais a n. Esta resposta é sobre o problema sem essa restrição. Desde o comentário de Emil sobre a questão refere-se ao problema com a restrição, não há contradição entre o seu comentário e a resposta seguinte.


O problema é NP-completo, mesmo que os números sejam dados unários.

O problema de 3 partições é o seguinte:
Instância : números inteiros positivos a 1 ,…, n em unário, onde n = 3m e a soma dos n números inteiros é igual a mB, de modo que cada a i satisfaça B / 4 < a i <B / 2.
Pergunta : Os números inteiros a 1 ,…, n podem ser particionados em m multisets para que a soma de cada multiset seja igual a B?

O problema de 3 partições é NP-completo, mesmo que 1 ,…, n sejam todos distintos [HWW08] (obrigado a Serge Gaspers por me falar sobre isso ). É possível reduzir esta versão restrita do problema de 3 partições para o problema em questão da seguinte maneira.

Suponha que recebamos uma instância do problema de 3 partições que consiste em números inteiros positivos distintos a 1 ,…, n . Seja m = n / 3 e B = (a 1 +… + a n ) / m, e seja N o máximo entre a i . Considere a seguinte instância do problema do stick: a instância consiste em um stick de comprimento k para cada k∈ {1,…, N} ∖ {a 1 ,…, a n } e m de comprimento B. Usando o fato que cada a i satisfaz a i > B / 4 ≥ N / 2, é fácil provar que esse problema de stick tem uma solução se e somente se a instância do problema de 3 partições tiver uma solução.

Referências

[HWW08] Heather Hulett, Todd G. Will, Gerhard J. Woeginger. Realizações multigráficas de seqüências de graus: a maximização é fácil, a minimização é difícil. Letters , 36 (5): 594–596, setembro de 2008. http://dx.doi.org/10.1016/j.orl.2008.05.004

Tsuyoshi Ito
fonte
3
Eu não sei se o problema de 3 partições permanece NP-completo ou não, se os números são distintos, e eu estou perguntando sobre isso: cstheory.stackexchange.com/questions/716/…
Tsuyoshi Ito
Serge Gaspers me disse que sim (obrigado!). Eu simplifiquei a prova usando-a.
Tsuyoshi Ito