Problema de la suma de subconjunts

El problema de la suma de subconjunts és un problema important en la teoria de la complexitat i en la criptografia. El problema és est: donat un conjunt de sancers, ¿existix algun subconjunt que la seua sumixca siga exactament zero? Per eixemple, donat el conjunt { −7, −3, −2, 5, 8}, la resposta és SI, perque el subconjunt { −3, −2, 5} suma zero. Este problema és NP-complet.

Un problema equivalent és: donat un conjunt de sancers i un sancer s, ¿existix algun subconjunt que la seua sumixca siga s? La suma de subconjunts també pot vore's com un cas especial del problema de la mochila.

Discussió general

El problema de la suma de subconjunts és una bona introducció als problemes NP-complets per dos raons:

• És un problema de decisió, no un d'optimisació i
• la seua definició és simple.

La majoria dels problemes físics poden ser resolts en un índex d'error de el +/- 1%. Resoldre un problema de suma de subconjunts per a 100 sancers en una precisió de +/-10^-100 pot semblar irrellevant, pero no ho és per dos raons.

Primer, el problema de la suma de subconjunts té una declaració precisa de la complexitat llògica d'una classe de problemes (els NP-complets). Resoldre-ho exactament significaria resoldre tots els problemes en esta classe. Resoldre-ho en un marge d'error de +/- 1% tornaria inútil a l'algoritme per a alguns atres problemes. Segon, en si més no un context, és de fet important resoldre el problema de la suma de subconjunts de manera exacta. En criptografia, este problema sorgix quan un asaltacódigos tracta de deduir la clau secreta a partir d'un mensage i la seua versió sifrada. Una clau a una distància de +/- 1% de la real és inservible.

Els casos en els que la solució aproximada és més que suficient ya han segut estudiats, en el camp dels algoritmes d'aproximació. Un d'eixos algoritmes és tractat més alvance.

Resolució

Pot considerar-se que la complexitat de la resolució del problema depén de dos paràmetros:

• N, el número de variables de decisió
• P, la precisió del problema, el número de valors de posicions binaria que pren definir el problema.

La complexitat dels algoritmes més coneguts és exponencial en el més chicotet dels dos paràmetros N i P. Per tant, el problema és més difícil si N i P són del mateix orde pero solament es torna més fàcil si algun dels dos es torna molt menut.

L'imposició de certes restriccions sobre la seqüència de sancers sobre la que s'opera, problema de la mochila simple, fan que la resolució del problema siga trivial seguint un algoritme definit. Este tipo de problemes és molt usat en criptografia.

Algoritme de temps exponencial

Hi ha vàries maneres de resoldre la suma de subconjunts en temps exponencial sobre N. L'algoritme més simplista verificaria tots els possibles subconjunts de N i, per a cada u d'ells, compararia la suma al total buscat. El temps d'eixecució és d'orde O(2^NN), ya que hi ha 2^N subconjunts i, per a verificar cada subconjunt, tenim que sumar N elements.

Es coneix un millor algoritme de temps exponencial, que corre en temps d'orde O(2^N/2N). L'algoritme partix els N elements en dos conjunts de N/2 elements cada u. Per a cada conjunt, calcula la suma de tots els 2^N/2 possibles subconjunts i les almagasena en un vector de llongitut 2^N/2. Llavors ordena estos dos vectores, lo que es pot fer en temps O(2^N/2N). Una volta que els vectores estan ordenats, l'algoritme pot verificar si un element del primer vector més un element del segon donen el total s buscat en temps O(2^N/2). Per a fer açò, l'algoritme passa pel primer vector en orde decreixent (escomençant en l'element més gran) i pel segon en orde creixent (escomençant pel més menut). Quan la suma de l'element en tanda dels dos vectores és major que s, l'algoritme es mou al següent element en el primer vector, quan és menor que s es mou al següent element en el segon vector. Si es troba s l'algoritme termina.

Resolució dinàmica de temps seudo-polinomial

El problema també pot ser resolt com seguix, utilisant programació dinàmica. Supongam que la seqüència de sancers està representada per

x₁,..., x_n

i volem trobar un subconjunt que la seua sumixca siga 0. Representem ´la suma de valors negatius en N i la suma de valors positius en P. Definim la funció booleana

Q(i, s)

com (verdadera o falsa) de

"existix un subconjunt de x₁,..., x_i que la seua suma és s".

(Per tant, el valor que realment busquem és Q(n,0).)

És clar que

Q(i, s) = fals

si s<N o s>P.

Crear una matriu per a guardar els valors de Q(i, s) per a 1≤i≤n i N≤s≤P. La matriu pot ser omplida en una recursión simple.

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

Per a i>1,

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

El número total d'operacions aritmètiques és

O(n(P - N)).

Per eixemple, si tots els valors són

O(n^k)

per a algun k, llavors el temps requerit és

O(n^k+1).

Esta solució no conta com de temps polinomial en teoria de complexitat perque P-N no és polinomial en el tamany del problema, que és el número de bits usats per a representar-ho.

Algoritme d'aproximació en temps polinòmic

Una versió aproximada de la suma de subconjunts seria: donat un conjunt de números N

x1, x2,..., xN 

i un número s, retornar

• si, quan existix un subconjunt que sumix s;
• no, si no existix un subconjunt que sumix algun total entre (1-c)s i s per a algun c>0 menut;
• qualsevol resposta, si algun subconjunt suma algun total entre (1-c)s i s pero cap suma s.

Si tots els números són no negatius, la suma de subconjunts aproximada és soluble en temps polinòmic per a N i 1/c.

Referències

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.