Si lo sé correctamente, el problema de la suma de subconjuntos es NP-completo. Aquí tiene una matriz de n enteros y se le da una suma objetivo t, debe devolver los números de la matriz que pueden sumar al objetivo (si es posible).
Pero, ¿no puede resolverse este problema en tiempo polinómico mediante un método de programación dinámica donde construimos una tabla n X t y tomamos casos como decir que el último número seguramente se incluye en la salida y luego el objetivo se convierte en t- a [n]. En otro caso, el último número no está incluido, entonces el objetivo permanece igual t pero la matriz se vuelve de tamaño n-1. Por lo tanto, así seguimos reduciendo el tamaño del problema.
Si este enfoque es correcto, ¿no es la complejidad de este n * t, que es polinomial? y si esto pertenece a P y también NP-completo (por lo que escucho) entonces P = NP.
Seguramente, me estoy perdiendo algo aquí. ¿Dónde está la escapatoria en este razonamiento?
Gracias,
Respuestas:
Su lógica es correcta, y lo que describió es un algoritmo válido de suma de subconjuntos que lo resuelve
O(nt).Sin embargo, este tipo de algoritmo es pseudopolinomial , lo que significa que es exponencial al número de bits utilizados para representar la entrada. Lo que eso significa es que si tu
tes 1000, entonces puedo hacer que tu programa sea 10 veces más lento agregando otro 0 (tahora es 10000).Entonces, si bien el algoritmo es polinomial al valor de
nyt, es exponencial al tamaño de la entrada (número de caracteres, bits, como quiera llamarlos, en la entrada).Y por lo tanto, este problema no está en P (a menos que P = NP o algo similar).
Fuente y lecturas adicionales
fuente