É o problema da mochila 0-1, onde o valor é igual ao peso NP-completo?

9

Tenho um problema que suspeito ser NP-completo. É fácil provar que é NP. Minha linha de pensamento atual gira em torno do uso de uma redução da mochila, mas resultaria em instâncias de 0-1-mochila com o valor de cada item igual ao seu peso.

Ainda está NP-completo? Ou eu estou esquecendo de alguma coisa?

complexity-theory np-complete decision-problem packing Zeta Two
fonte
Isso é muito tarde, mas de qualquer maneira: sua redação sugere que você pode estar tentando reduzir na direção errada. Você precisa reduzir da mochila para o seu problema, o que significa que você deve permitir instâncias arbitrárias da mochila (que podem produzir instâncias do seu problema que tenham alguma estrutura especial) - nenhuma parte deste procedimento "resultaria em" instâncias da mochila com algumas especialidades estrutura. (OTOH, faz sentido perguntar se algum caso especial da mochila ainda é NP-completo, uma vez que pode ser mais fácil de reduzir de.)
j_random_hacker
Sim. O que eu quis dizer foi que reduzi da mochila, mas especificamente da "mochila 0-1, com o valor de cada item igual ao seu peso". Então, era apenas a minha redação que estava um pouco errada.
Zeta Two

Respostas:

9

Sim, isso é chamado de problema de soma de subconjuntos e é NP-Hard.

Aryabhata
fonte
Obrigado! Acabei de perceber que fiz essa descoberta anteriormente. Infelizmente, também percebi que minha redução não funcionou. De volta à prancheta. :(
Zeta Two
@ZetaTwo: Você é bem-vindo :-)
Aryabhata