Diferencia entre revisiones de «Problema de la suma de subconjuntos»
Contenido eliminado Contenido añadido
Deshecha la edición 11756621 de 201.238.237.140 (disc.) |
|||
Línea 14:
Primero, el problema de la suma de subconjuntos tiene una declaración precisa de la complejidad lógica de una clase de problemas (los NP-completos). Resolverlo exactamente significaría resolver todos los problemas en esta clase. Resolverlo con un margen de error de +/- 1% volvería inútil al algoritmo para algunos otros problemas. Segundo, en cuando menos un contexto, es de hecho importante resolver el problema de la suma de subconjuntos de manera exacta. En criptografía, este problema surge cuando un asaltacódigos trata de deducir la llave secreta a partir de un mensaje y su versión cifrada. Una llave a una distancia de +/- 1% de la real es inservible.
Los casos en los que la solución aproximada es más que suficiente ya han sido estudiados, en el campo de los [[algoritmos de aproximación]]. Uno de esos algoritmos es tratado más adelante.
==La complejidad de la suma de subconjuntos==
| |||