Subset Sum and the Secret Language of Numbers
Kent Quanrud · 57:13
La clase demuestra que subset sum (decidir si algún subconjunto de enteros suma exactamente un objetivo \(T\)) es tan difícil como 3-SAT: el DP clásico \(O(nT)\) no es polinómico en el tamaño de la entrada, y existe u...