¿Existe una estructura de datos con complejidad espacial exponencial?

Sostenga mi cerveza.

Suponga que desea resolver el problema de la suma de subconjuntos y se le permite hacer la precomputación que desee, pero necesita devolver una respuesta en línea de la manera más eficiente posible. Es decir, obtendremos entradas [matemáticas] x_1, x_2, … x_n [/ matemáticas]. En algún momento del año que viene se nos dará [math] y_1, y_2,…, y_m [/ math], y desea saber qué subconjunto de las [math] x [/ math], si las hay, suman a cada [math] y [/ math] dado.

¿Qué tan grande es una lista precalculada de posibles valores [matemáticos] y [/ matemáticos], en el peor de los casos? Si las [math] x [/ math] son ​​linealmente independientes (sobre los racionales, o incluso sobre los enteros, o incluso sobre [math] \ {0, 1 \} [/ math]) entonces hay [math ] 2 ^ {n} [/ math] valores para los que queremos devolver “verdadero”.

Por lo tanto, una estructura de datos de tamaño exponencial para este problema es calcular todos los subconjuntos [math] 2 ^ {n} [/ math] de [math] x_i [/ ​​math], tomar las sumas resultantes y ponerlas todas en una tabla hash perfecta indexada por las sumas. Cada [matemática] y [/ matemática] se puede buscar en [matemática] O (1) [/ matemática].

De hecho, si [math] m = \ Theta (2 ^ n) [/ math], ¡hemos logrado un tiempo constante amortizado para toda la operación! No está mal para un problema NP-completo.