El problema de la suma de subconjuntos es un problema importante en la teoría de la complejidad y en la criptografía. El problema es este: dado un conjunto de enteros, ¿existe algún subconjunto cuya suma sea exactamente cero? Por ejemplo, dado el conjunto { −7, −3, −2, 5, 8}, la respuesta es SI, porque el subconjunto { −3, −2, 5} suma cero. Este problema es probablemente el más simple de explicar de los problemas NP-completos.

Un problema equivalente es: dado un conjunto de enteros y un entero s, ¿existe algún subconjunto cuya suma sea s? La suma de subconjuntos también puede verse como un caso especial del problema problema de la mochila.

Contenido 1 Discusión general 2 La complejidad de la suma de subconjuntos 3 Algoritmo de tiempo exponencial 4 Solución dinámica de tiempo seudo-polinomial 5 Algoritmo de aproximación en tiempo polinómico 6 Referencias

Discusión general

El problema de la suma de subconjuntos es una buena introducción a los problemas NP-completos por dos razones:

• Es un problema de decisión, no uno de optimización y
• su definición es simple.

La mayoría de los problemas físicos pueden ser resueltos con un índice de error del +/- 1%. Resolver un problema de suma de subconjuntos para 100 enteros con una precisión de +/-10⁻¹⁰⁰ puede parecer irrelevante, pero no lo es por dos razones.

Primero, el problema de la suma de subconjuntos tiene una declaración precisa de la complejidad lógica de una clase de problemas (los NP-completos). Resolverlo exactamente significaría resolver todos los problemas en esta clase. Resolverlo con un margen de error de +/- 1% volvería inútil al algoritmo para algunos otros problemas. Segundo, en cuando menos un contexto, es de hecho importante resolver el problema de la suma de subconjuntos de manera exacta. En criptografía, este problema surge cuando un asaltacódigos trata de deducir la llave secreta a partir de un mensaje y su versión cifrada. Una llave a una distancia de +/- 1% de la real es inservible.

Los casos en los que la solución aproximada es más que suficiente ya han sido estudiados, en el campo de los algoritmos de aproximación. Uno de esos algoritmos es tratado más adelante.

La complejidad de la suma de subconjuntos

Puede considerarse que la complejidad depende de dos parámetros. N, el número de variables de decisión y P, la precisión del problema (número de valores de posiciones binaria que toma definir el problema).

La complejidad de los algoritmos más conocidos es exponencial en el más pequeño de los dos parámetros N y P. Por tanto, el problema es más difícil si N y P son del mismo orden pero solo se vuelve más fácil si alguno de los dos se vuelve muy pequeño.

Algoritmo de tiempo exponencial

Hay varias maneras de resolver la suma de subconjuntos en tiempo exponencial sobre N. El algoritmo más inocente verificaría todos los posibles subconjuntos de N y, para cada uno de ellos, compararía la suma al total buscado. El tiempo de ejecución es de orden O(2^NN), dado que hay 2^N subconjuntos y, para verificar cada subconjunto, tenemos que sumar N elementos.

Se conoce un mejor algoritmo de tiempo exponencial, que corre en tiempo de orden O(2^N/2N). El algoritmo parte los N elementos en dos conjuntos de N/2 elementos cada uno. Para cada conjunto, calcula la suma de todos los 2^N/2 posibles subconjuntos y las almacena en un vector de longitud 2^N/2. Entonces ordena estos dos vectores, lo que se puede hacer en tiempo O(2^N/2N). Una vez que los vectores están ordenados, el algoritmo puede verificar si un elemento del primer vector más un elemento del segundo dan el total s buscado en tiempo O(2^N/2). Para hacer esto, el algoritmo pasa por el primer vector en orden decreciente (empezando en el elemento más grande) y por el segundo en orden creciente (empezando por el más pequeño). Cuando la suma del elemento en turno de los dos vectores es mayor que s, el algoritmo se mueve al siguiente elemento en el primer vector, cuando es menor que s se mueve al siguiente elemento en el segundo vector. Si se encuentra s el algoritmo termina.

Solución dinámica de tiempo seudo-polinomial

El problema también puede ser resuelto como sigue, utilizando programación dinámica. Supongamos que la secuencia de enteros está representada por

x₁,..., x_n

y queremos encontrar un subconjunto cuya suma sea 0. Representemos ´la suma de valores negativos con N y la suma de valores positivos con P. Definamos la función booleana

Q(i, s)

como (verdadera o falsa) de

"existe un subconjunto de x₁,..., x_i cuya suma es s".

(Por tanto, el valor que realmente buscamos es Q(n,0).)

Es claro que

Q(i, s) = falso

si s<N o s>P.

Crear una matriz para guardar los valores de Q(i, s) para 1≤i≤n y N≤s≤P. La matriz puede ser llenada con una recursión simple.

Q(1,s) = "s=0 or x₁=s".

Para i>1,

Q(i, s) = Q(i-1,s) o Q(i-1,s-x_i).

El número total de operaciones aritméticas es

O(n(P − N)).

Por ejemplo, si todos los valores son

O(n^k)

para algún k, entonces el tiempo requerido es

O(n^k+1).

Esta solución no cuenta como de tiempo polinomial en teoría de complejidad porque P-N no es polinomial en el tamaño del problema, que es el número de bits usados para representarlo.

Algoritmo de aproximación en tiempo polinómico

Una versión aproximada de la suma de subconjuntos sería: dado un conjunto de números N

x1, x2,..., xN 

y un número s, regresar

• si, cuando existe un subconjunto que sume s;
• no, si no existe un subconjunto que sume algún total entre (1-c)s y s para algún c>0 pequeño;
• cualquier respuesta, si algún subconjunto suma algún total entre (1-c)s y s pero ninguno suma s.

Si todos los números son no-negativos, la suma de subconjuntos aproximada es soluble en tiempo polinómico para N y 1/c.

Referencias

de Wikipedia en inglés

1. T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001. Chapter 35.5, The subset-sum problem.
2. Michael R. Garey and David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, 1979, W.H. Freeman. ISBN 0716710455 A3.2: SP13, pg.223.

el sub conjunto es todo elementoque aparte del elemento tiene algo más a eso sele llama sub algo adicional