Otra variante de PARTICION

Tengo una reducción del siguiente problema de partición a un cierto problema de programación:

Entrada: Una lista de enteros positivos en orden no decreciente.$a_1\leqslant\cdots\leqslant a_n$

Pregunta: ¿Existe un vector $(x_1,\ldots,x_n)\in\{-1,1\}^n$ tal que

Sin la segunda condición, es solo PARTICIÓN, por lo tanto, NP-hard. Pero la segunda condición parece proporcionar mucha información adicional. Me pregunto si hay una manera eficiente de decidir esta variante. ¿O sigue siendo difícil?

Aquí hay una reducción de PARTICIÓN a este problema. Deje $(a_1,\dots, a_n)$ ser una instancia de PARTITION. Suponga que $a_1\leq a_2\leq \dots \leq a_n$ .

Sea un "número muy grande", por ejemplo, . Considere la instancia de nuestro problema.N = ( ∑ n i = 1 | a i | ) + 1 N , … , N ⏟ 5 n  veces , N + a 1 , … , N + a n , 4 N , … , 4 N ⏟ n $N$$N = (\sum_{i=1}^n |a_i|) + 1$

1. Si hay una solución para PARTITION, entonces es una solución a nuestro problema.1 , … , 1 ⏟ 4 n  veces , - x 1 , … , - x n , x 1 , … , x n , - 1 , … , - 1 ⏟ n $x_1,\dots, x_n$

   $$\underbrace{1, \dots, 1}_{4n \text{ times}},-x_1,\dots,-x_n,x_1,\dots,x_n,\underbrace{-1,\dots,-1}_{n \text{ times}}$$

2. Si hay una solución a la instancia de nuestro problema (al que redujimos una instancia de PARTITION), entonces . Por lo tanto, Es decir, es una solución para PARTICIÓN.$(x_1,\dots,x_{5n},y_1,\dots, y_n, z_1,\dots,z_n)$$\sum_{i=1}^n a_i y_i \equiv 0 \pmod N$

   $$\sum_{i=1}^n a_i y_i = 0.$$ $(y_1,\dots, y_n)$