¿El problema de la mochila 0-1 es donde el valor es igual al peso NP completo?

9

Tengo un problema que sospecho es NP-completo. Es fácil demostrar que es NP. Mi actual tren de pensamiento gira en torno al uso de una reducción de la mochila, pero daría como resultado casos de 0-1-mochila con el valor de cada elemento igual a su peso.

¿Sigue siendo NP completo? ¿O me estoy perdiendo algo?

complexity-theory np-complete decision-problem packing Zeta Two
fuente
Esto es años demasiado tarde, pero de todos modos: su redacción sugiere que podría estar tratando de reducir en la dirección incorrecta. Es necesario reducir de mochila a su problema, lo que significa que tiene que permitir arbitrarias casos de mochila (que pueden producir casos de su problema que tienen alguna estructura especial) - Ninguna parte de este procedimiento "número de" casos de mochila con algo de especial estructura. (OTOH, tiene sentido preguntar si algún caso especial de Mochila todavía tiene NP completo, ya que podría ser más fácil reducirlo.)
j_random_hacker
Si. Lo que quise decir es que reduzco de la mochila, pero específicamente de la "mochila de 0-1 con el valor de cada elemento igual a su peso". Entonces, fue solo mi redacción la que estaba un poco fuera de lugar.
Zeta Two

Respuestas:

9

Sí, esto se llama problema de suma de subconjuntos y es NP-Hard.

Aryabhata
fuente
¡Gracias! Me acabo de dar cuenta de que hice ese descubrimiento antes. Lamentablemente, también me di cuenta de que mi reducción no funcionó en absoluto. De vuelta al tablero de dibujo. :(
Zeta Two
@ZetaTwo: De nada :-)
Aryabhata