O Problema da Soma dos Subconjuntos

TECNICAS DE PESQUISA E ORDENAÇAO I

COLATINA
2013

1. O Problema da Soma de Subconjuntos

O problema da soma de subconjuntos é um importante problema da teoria da complexidade computacional e criptografia. O problema é este: dado um conjunto de inteiros, existe um subconjunto não-vazio cuja soma é 0? Por exemplo, dado o conjunto { −7, −3, −2, 5, 8}, a resposta é sim porque o subconjunto { -3, -2, 5} resulta numa soma que dá zero. O problema é NP-completo.
Um problema equivalente é este: dado um conjunto de inteiros e um inteiro s, existe algum subconjunto que some s? Um caso interessante de soma subconjunto é o problema de partição, em que s é a metade da soma de todos os elementos do conjunto.

2. Complexidade

A complexidade da soma de subconjuntos poderá ser vista de dois parâmetros, N, o número de variáveis de decisão, e P, a precisão do problema.
A complexidade do melhor algoritmo conhecido é exponencial no menor dos dois parâmetros N e P. Assim, o problema é mais difícil se N e P são da mesma ordem.
O que acontece é que o problema se torna aparentemente não-exponencial quando se é prático para considerar o espaço da solução. Existem duas maneiras de medir o espaço de solução do Problema da soma dos subconjuntos. Uma delas é contar o número de maneira que as variáveis podem ser combinadas. Existem 2N possíveis maneiras de combinar as variáveis. Contudo, com N = 10, existem somente 1024 possíveis combinações para checar. A outra maneira é considerar a combinação de todos os valores numéricos possíveis. Estes poderão ser contados facilmente com um algoritmo de programação dinâmica. Quando N = P e ambos são grandes, então não há nenhum aspecto do espaço de soluções que podem ser contados facilmente.

3. Algoritmo de tempo exponencial

Existem muitas maneiras de resolver o problema da soma de subconjunto em tempo exponencial em N. O algoritmo mais ingênuo percorreria todos os