Tengo un subconjunto$S=\{x_1, x_2, x_3, ... x_m\}$ con$m$ elementos en él. Cada uno de estos elementos se encuentra entre$1$ y$m^2$. Dada una instancia de este problema y una suma,$y$, quiero colocar un límite superior en el número de subconjuntos de$S$ que puede sumar a$y$. Cualquier límite superior polinómico crudo funcionaría para mí. (Necesito este límite superior para alguna prueba que estoy construyendo para un problema de criptografía).
Respuesta
¿Demasiados anuncios?
Si todos los elementos son iguales a$1$ y$y = m/2$, entonces el número de subconjuntos es$$\binom{m}{m/2} = \Theta\left(\frac{2^m}{\sqrt{m}}\right).$ $
Aquí hay un ejemplo con todos los elementos diferentes. Deje$S = \{1,\ldots,m\}$ y$y = (m+1)m/4$. El número de subconjuntos es al menos$$\binom{m/2}{m/4} = \Theta\left(\frac{2^{m/2}}{\sqrt{m}}\right).$ $
