Еще один вариант PARTITION

У меня сведение следующей проблемы с разделом к ​​определенной проблеме планирования:

Входные данные: список целых положительных чисел в неубывающем порядке.$a_1\leqslant\cdots\leqslant a_n$

Вопрос: существует ли вектор такой, что$(x_1,\ldots,x_n)\in\{-1,1\}^n$

k ∑ i = 1 a i x i ⩾

Без второго условия это просто РАЗДЕЛЕНИЕ, следовательно, NP-hard. Но второе условие, кажется, дает много дополнительной информации. Мне интересно, есть ли эффективный способ решить этот вариант. Или это все еще сложно?

Вот сокращение от PARTITION к этой проблеме. Пусть $(a_1,\dots, a_n)$ будет экземпляром PARTITION. Предположим, что $a_1\leq a_2\leq \dots \leq a_n$ .

Пусть будет «очень большим числом», например, . Рассмотрим экземпляр нашей проблемы.$N$$N = (\sum_{i=1}^n |a_i|) + 1$

1. Если существует решение для PARTITION, то - это решение нашей проблемы.$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. Если есть решение экземпляра нашей проблемы (к которому мы сократили экземпляр PARTITION), то . Таким образом, То есть является решением для 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)$