La pregunta está esencialmente en el título.
Estoy trabajando con reducciones de tiempo polinómico, pero me imagino que esta parte de la pregunta es más relevante para las Matemáticas, en lugar de la Informática.
Esencialmente, en el problema de partición, el objetivo es dividir un subconjunto de enteros M en dos subconjuntos, $S_1 $ y $S_2$ , de tal manera que $\sum_{e \in S_1} e = \sum_{e \in S_2} e$ . Por supuesto, no todos los conjuntos múltiples pueden hacer esto $\{2, 5\}$ por ejemplo, y algunos tienen más de una solución única, por ejemplo $\{1, 1, 1, 2, 2, 3\}$ .
¿Es matemáticamente correcto decir que la partición $M + M$ en subconjuntos $S_i$ para $i \in \{1, 2, 3, 4\}$ es decir, duplicar los elementos en $M$ y duplicando los subconjuntos a particionar, se obtendrán cuatro subconjuntos de igual suma, si el conjunto original se puede dividir en 2?
Supongo que una forma más rigurosa de expresar esto sería:
Si $f(s, k) = $ set $s$ puede dividirse en $k$ subconjuntos, tales que todos los subconjuntos tienen enteros con igual suma:
$f(S,2) \iff f(S + S, 4)$
O de forma más generalizada,
$f(S, 2^x) \iff f(\sum_{i=1}^{x+1} S, 2^{x+1})$
Dudo que el caso generalizable sea cierto, pero ¿es cierto el caso 2>4? Y si no, como pregunta al margen, ¿alguien sabe cómo encontrar algún conjunto $M$ tal que $f(S,2) \iff f(M, 4)$ ?
Pido disculpas si esta pregunta es poco clara u obvia, mi formación no es del todo matemática.
0 votos
Utilizando las notaciones estándar, $M \cup M = M$ . Se podría definir $ M + M$ , a veces se utiliza para representar la unión disjunta.
0 votos
¿Hay alguna forma de demostrar con notación matemática que un multiconjunto contiene exactamente el mismo contenido de un multiconjunto dos veces?
1 votos
Como si $M = \{1, 3, 3\}$ entonces $M + M = \{1, 1, 3, 3, 3, 3\}$ .