Problema de la suma de subconjuntos

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 NP-completo.

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 de la mochila.

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^-100 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.

Resolución

Puede considerarse que la complejidad de la resolución del problema depende de dos parámetros:

N, el número de variables de decisión
P, la precisión del problema, el 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.

La imposición de ciertas restricciones sobre la secuencia de enteros sobre la que se opera, problema de la mochila simple, hacen que la resolución del problema sea trivial siguiendo un algoritmo definido. Este tipo de problemas es muy usado en criptografía.

Algoritmo de tiempo exponencial

Hay varias maneras de resolver la suma de subconjuntos en tiempo exponencial sobre N. El algoritmo más simplista 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.

Resolució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

x₁, x₂,..., x_N

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

T. Cormen, C. Leiserson, R. Rivest. Introduction to Algorithms. MIT Press, 2001. Chapter 35.5, The subset-sum problem.
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.

Datos: Q1154420