Todavía es -completo, incluso para . Dada una instancia de suma de subconjuntos, podemos transformarla en esta variante dividiendo los números y agregando algunos bits adicionales. k = 2NPk=2
Primero, la suma de todos los números en el problema será menor que para algún valor de . m2mm
Ahora, tomemos un número del problema original que tiene bits establecidos. Dividiremos este número en números con exactamente 2 bits establecidos de modo que la suma de esos números sea . Podemos hacer esto de forma recursiva, encontrando números que suman los primeros bits más y números que resumir hasta el último bits más .k k n + 2 k + m ⌈ k ⌉ ⌈ k ⌉ 2 k + m - 1 ⌊ k ⌋ ⌊ k ⌋ 2 k + m - 1nkkn+2k+m⌈k⌉⌈k⌉2k+m−1⌊k⌋⌊k⌋2k+m−1
Además de ese número, también agregaremos el número al problema. Una solución debe contener este número o todos los números construidos previamente. Si el valor objetivo original era el nuevo valor objetivo será . k t t + 2 k + m2k+mktt+2k+m
Si el problema original tenía más de un número, podemos repetir este proceso tomando para el nuevo valor de .mk+m+1m
Solo hay dos formas de establecer el bit en la posición : la respuesta puede contener el número o todos los números que suman . Por lo tanto, hemos reducido la suma de subconjuntos a su variante de suma de subconjuntos.2 k + m k n + 2 k + mk+m2k+mkn+2k+m
Como ejemplo, tomemos con el valor objetivo . Este problema podría codificarse como la variante de suma de subconjuntos presentada aquí tomando los siguientes números binarios:{2,3,5}7
2 se asigna a y . (Usar el bit extra no es estrictamente necesario aquí).0100 10000 1
3 se asigna a y1000 00 1,0100 00 10000 00 01
5 se asigna a y .1000 00 000 1,0010 00 000 10000 00 000 01
El nuevo valor objetivo se convertiría en .1110 10 010 01
Si el problema original se representa con bits, entonces el problema transformado tiene como máximo bits. El problema original tendrá como máximo números cada uno con como máximo bits, por lo que la suma de todos ellos también es O (n). El problema transformado tendrá números (ya que cada número de bits se divide en números de bits, siendo su longitud como máximo ya que usamos bits adicionales para cada número, de modo que el tamaño total del problema transformado es bits.O ( n 4 ) O ( n ) O ( n ) O ( n 2 ) n n + 1 2 O ( n 2 ) n O ( n 4 )nO(n4)O(n)O(n)O(n2)nn+1 2O(n2)nO(n4)
Esta es información extraída de la pregunta de Vor.
Para el problema sigue siendo NP completo. Encontré una reducción rápida del monótono X-SAT ( vea el esquema de la reducción aquí ).k≥3
El problema sigue siendo NP completo incluso si , vea la respuesta de Tom para más detalles. Aquí hay una pequeña representación de su reducción de SUBSET SUM:k=2
fuente