Se eu sei corretamente, o problema da soma do subconjunto é NP-completo. Aqui você tem uma matriz de n números inteiros e recebe uma soma alvo t, é necessário retornar os números da matriz que podem somar à meta (se possível).
Mas esse problema não pode ser resolvido no tempo polinomial pelo método de programação dinâmica, onde construímos uma tabela n X t e tomamos casos como digamos que o último número certamente está incluído na saída e, em seguida, o destino se torna t-a [n]. Em outro caso, o último número não é incluído, então o destino permanece o mesmo t, mas a matriz se torna do tamanho n-1. Portanto, continuamos reduzindo o tamanho do problema.
Se essa abordagem estiver correta, a complexidade desse n * t não é polinomial? e assim, se isso pertence a P e também NP-completo (pelo que ouvi), então P = NP.
Certamente, estou perdendo alguma coisa aqui. Onde está a brecha nesse raciocínio?
Obrigado,
Respostas:
Sua lógica está correta - e o que você descreveu é um algoritmo de soma de subconjuntos válido que a resolve
O(nt).No entanto, esse tipo de algoritmo é pseudopolinomial , o que significa que é exponencial ao número de bits usados para representar a entrada. O que isso significa é que, se você
té 1000, posso tornar seu programa 10 vezes mais lento adicionando outro 0 a ele (tagora é 10000).Portanto, enquanto o algoritmo é polinomial ao valor de
net, é exponencial ao tamanho da entrada (número de caracteres, bits, o que você quiser chamá-los, na entrada).E, portanto, esse problema não está em P (a menos que P = NP ou algo semelhante).
Fonte e leitura adicional
fonte