Une autre variante de PARTITION

J'ai une réduction du problème de partition suivant à un certain problème de planification:

Entrée: Une liste $a_1\leqslant\cdots\leqslant a_n$ d'entiers positifs dans l'ordre non décroissant.

Question: Existe-t-il un vecteur $(x_1,\ldots,x_n)\in\{-1,1\}^n$ tel que

Sans la deuxième condition, c'est juste PARTITION, donc NP-hard. Mais la deuxième condition semble fournir beaucoup d'informations supplémentaires. Je me demande s'il existe un moyen efficace de décider de cette variante. Ou est-ce toujours difficile?

Voici une réduction de PARTITION à ce problème. Soit $(a_1,\dots, a_n)$ une instance de PARTITION. Supposons que $a_1\leq a_2\leq \dots \leq a_n$ .

Soit un «très grand nombre», par exemple . Considérez l'instance de notre problème.N = ( ∑ n i = 1 | a i | ) + 1 N , … , N ⏟ 5 n  fois , N + a 1 , … , N + a n , 4 N , … , 4 N ⏟ n $N$$N = (\sum_{i=1}^n |a_i|) + 1$

1. S'il existe une solution à PARTITION alors est une solution à notre problème.1 , … , 1 ⏟ 4 n  fois , - 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. S'il existe une solution à l'instance de notre problème (à laquelle nous avons réduit une instance de PARTITION), alors . Ainsi Autrement dit, est une solution à PARTITION.$(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)$