La decisión problema de si una secuencia se puede dividir en $k$ subsecuencias que se suma a $0$ es de hecho NP-completo. Para mostrar esto, se puede reducir el 3-problema de partición (que es fuertemente NP-completo) para esto.
3-problema de partición (mejor formulación de esta reducción): Dada una secuencia $x_1,\ldots,x_{3n}$ de los enteros entre $B/2$$B/4$, que suma a $Bn$, determinar si existe una partición de $x_1,\ldots,x_{3n}$ en triples que cada suma a $B$. Podemos suponer $B$ es acotado por un polinomio en $n$.
Reducción: Vamos A $N=\max\{4n,B\}$. Considerar la secuencia de $N$ enteros entre $-N$ $N$ dada por
$$x_1,x_2,x_3,-B,\ldots,x_{3n-2},x_{3n-1},x_{3n},-B,0,\ldots,0$$
que ha $m=N-4n$ ceros. El original 3-partición problema es equivalente a si existe una partición de esta secuencia en $n+m$ subsecuencias que se suma a $0$.
Prueba: Si la partición de la secuencia original en triples $(x_{i_1},x_{i_2},x_{i_3})$ que agregar $B$ existe entonces la $n$ subsecuencias $(x_{i_1},x_{i_2},x_{i_3},-B)$ $m$ subsecuencias $(0)$ total $0$. Por el contrario, tenga en cuenta que si una larga sumas a $0$ y contiene un término distinto de cero, entonces debe de contener al menos $4$ cero términos, es decir, tres $x_i$ $-B$ todos los $x_i$ son positivos y se necesitan al menos $3$ agregar a a $B$. Así, la secuencia se puede dividir en en la mayoría de las $n+m$ subsecuencias que añaden a las $0$, y la única manera de hacer esto es si $n$ de las subsecuencias son de la forma $(x_{i_1},x_{i_2},x_{i_3},-B)$ y el otro $m$ son sencillamente $(0)$. Por lo tanto, si se puede dividir en $n+m$ subsecuencias, tenemos $n$ triples $(x_{i_1},x_{i_2},x_{i_3})$ que añadir a $B$.
