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:

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.

Other Languages