El problema es NP-completo.
Como referencia, a continuación llamaré a este problema el mismo problema de división promedio (SAS).
Khalil Sawant tiene la observación correcta sobre los promedios, pero luego comete el error común de hacer la reducción en la dirección incorrecta. Para demostrar que un nuevo problema es difícil, necesitamos reducir un problema viejo, ya conocido por ser difícil, al nuevo, no al revés. (Puedo reducir el viaje de NYC a LA a viajar a la luna y viceversa, pero la existencia de esta reducción no significa que viajar de NYC a LA sea difícil).
- ¿Existe evidencia de que el algoritmo de sugerencia de música basada en el genoma de Pandora es mejor que los algoritmos de recomendación estándar?
- Cómo escribir un código para un árbol en estructuras de datos
- ¿Cuál es la complejidad del tiempo para la escalera de palabras?
- ¿Por qué los algoritmos de compresión de datos sin pérdida no funcionan bien en archivos de video?
- Cómo escribir un script de fuerza bruta, en Eclipse
Nuestro problema está obviamente en NP. Para mostrar que es NP-hard, podemos reducir el problema de la suma de subconjuntos a nuestro problema de la siguiente manera:
Considere cualquier instancia del problema de suma de subconjuntos. Es decir, tenemos algunos valores [math] a_1, \ dots, a_n [/ math] y queremos decidir si algún subconjunto no vacío de [math] a_i [/ math] s se suma a cero.
Deje [math] s = \ sum a_i [/ math]. (Es decir, [math] s [/ math] es la suma actual de todos los elementos).
Si [math] s [/ math] es 0, simplemente tenemos que resolver el problema de SAS para esta instancia en particular.
De lo contrario, considere la siguiente instancia: [math] (a_1, \ dots, a_n, -s) [/ math]. Afirmamos que SAS tiene una solución para esta nueva instancia si y solo si Subset Sum tenía una solución para la instancia original.
¿Porqué es eso? Nuestra nueva instancia de SAS tiene suma cero, por lo tanto, estamos buscando dos partes no vacías que tengan suma cero. El elemento [math] -s [/ math] debe terminar en una de las dos partes. Y como [math] s \ not = 0 [/ math], esta parte debe contener al menos otro número. Por lo tanto, cada solución a SAS para la nueva instancia nos da una solución de Subset Sum para la instancia original. La dirección opuesta se puede verificar de manera similar.
Por lo tanto, resolver SAS es al menos tan difícil como resolver Subset Sum.
(Agradecimientos a Robert Johnson por simplificar mi reducción original).
