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?
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).
reference-request
complexity-classes
puzzles
Jagadish
fonte
fonte
Respostas:
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
fonte