Fórmula para todas las sumas posibles de una secuencia binaria

Question

Supongamos que tengo una secuencia, en la que para cada elemento puedo elegir uno de entre dos números. Me gustaría encontrar una fórmula compacta para escribir todas las sumas posibles de todas las secuencias posibles.

Por ejemplo, supongamos que tengo $\langle(1,2), (3,4) \rangle$

Las secuencias posibles son $\langle 1, 3 \rangle$ , $\langle 1, 4 \rangle$ , $\langle 2, 3\rangle$ , $\langle 2, 4\rangle$ y por lo tanto todas las sumas posibles son $4, 5, 5, 6$ respectivamente.

Answer 1

Parece que se cumple lo siguiente. Supongamos que la fórmula compacta es tan buena que es efectivamente computable (lo que, en general, probablemente, no es cierto, por ejemplo, para una fórmula $\tan 2^{2^n}$ (?)). A continuación, para ser independientes de la definición de un algoritmo de cálculo, suponemos que el Tesis de Church-Turing . Entonces su pregunta tiene una respuesta (aunque sólo consideremos enteros no negativos) porque pregunta por un Problema NP-completo . De hecho, por un lado, el problema de la suma de listas está en NP porque puede resolverse mediante $2^n$ autómatas independientes en tiempo lineal. Por otro lado, dado un conjunto $A=\{a_1,\dots, a_n\}$ de números naturales y un número natural $b$ para decidir si existe un subconjunto de $A$ cuya suma es $b$ es un problema de decisión bien conocido; el problema de la suma de subconjuntos que es NP-difícil . Por tanto, si consideramos los pares $\langle (a_1,0),\dots, (a_n,0)\rangle$ el problema de decidir si $b$ es la suma de una secuencia posible también es NP-difícil. A la inversa, decidir si $b$ es la suma de una secuencia posible de los pares $\langle (a_1,b_1),\dots, (a_n,b_n)\rangle$ basta con decidir si $b-(a_1+\cdots+a_n)$ es la suma de una secuencia posible de un submultiset de a multiset $\{b_1-a_1,\dots, b_n-a_n\}$ .

Agradecimientos. El autor agradece a Prof. Dr. Alexander Wolff por sus valiosas observaciones y correcciones.