Se lo so correttamente, il problema della somma del sottoinsieme è NP-completo. Qui hai una matrice di n interi e ti viene assegnata una somma di destinazione t, devi restituire i numeri dall'array che può riassumere fino alla destinazione (se possibile).
Ma non è possibile risolvere questo problema in tempo polinomiale con il metodo di programmazione dinamica in cui costruiamo una tabella n X t e prendiamo casi come dire che l'ultimo numero è sicuramente incluso nell'output e quindi il target diventa t- a [n]. In altri casi, l'ultimo numero è not incluso, quindi il target rimane lo stesso t ma l'array diventa di dimensione n-1. Quindi in questo modo continuiamo a ridurre le dimensioni del problema.
Se questo approccio è corretto, non è la complessità di questo n * t, che è polinomiale? e quindi se questo appartiene a P e anche NP-completo (da quello che sento) allora P = NP.
Sicuramente, mi manca qualcosa qui. Dov'è la scappatoia in questo ragionamento?
Grazie,