Encontrei o problema P vs NP há algum tempo e recentemente trabalhei no problema de soma de subconjuntos. Eu li um artigo da Wikipedia sobre o problema de Subconjunto de Soma, bem como a pergunta Algoritmo de Subconjunto de Soma
Eu olhei para o problema e encontrei algumas soluções, mas até agora elas parecem NP, acredito que posso criar um algoritmo suficientemente rápido no tempo NP.
Meu problema é que eu não sou bom em teoria, então não me ajuda muito falar sobre o teorema de Cook-Levin ou máquinas de Turing não determinísticas.
O que eu gostaria é uma explicação do subconjunto de programação dinâmica de tempo pseudo-polinomial que é encontrado na Wikipedia.
Eu li e acredito que entendo o conceito geral de por que é NP em vez de P (relacionado ao tamanho da entrada e não às operações com ela), mas não entendo o algoritmo.
Eu apreciaria se alguém colocasse um exemplo com alguns números e como ele funciona. Isso me ajudaria muito porque:
- Dê-me ideias para melhorar meu futuro algoritmo
- Ajude-me a entender intuitivamente quando um algoritmo é pseudo-polionial em vez de NP.
fonte
Respostas:
Reformulando o comentário de Kaveh como resposta:
Se você limitar o tamanho dos valores na entrada (limite o número de bits para cada valor a ser logarítmico no número total de bits da entrada), o problema poderá ser resolvido em tempo polinomial usando programação dinâmica. Se não estiverem delimitados, podem ter valores exponencialmente grandes e o tamanho da tabela para a programação dinâmica seria exponencial.
fonte