Линейная система со свободными членами особого вида

[lofar]

При решении одной прикладной задачи возникла следующая проблема.


Заданы целые числа $\Delta_1,\ldots,\Delta_s$ и $w_1,\ldots,w_s$ такие, что $0\le w_i\le\Delta_i,\;\; i=1\ldots s.$ Двоичный вектор (т.е. вектор с элементами из множества $\{0,1\}$) ${\bf b}=(b_1,\ldots,b_m)$ длины $m=\Delta_1+\ldots+\Delta_s$ назовем правильным если

в подвекторе $(b_1,\ldots,b_{\Delta_1})$ имеется ровно $w_1$ единиц,
в подвекторе $(b_{\Delta_1+1},\ldots,b_{\Delta_1+\Delta_2})$ имеется ровно $w_2$ единиц,
...
в подвекторе $(b_{\Delta_1+\ldots+\Delta_{s-1}+1},\ldots,b_m)$ имеется ровно $w_s$ единиц.

Иными словами, правильный вектор, это вектор составленный из $s$ блоков длин $\Delta_1,\ldots,\Delta_s$, причем $t$-й блок содерхит $w_t$ единиц (остальные элементы равны $0$).

Рассмотрим ситсему линейных уравнений над $\mathbb Z_2$ (левые части фиксированы):

$$ \left\{ \begin{array}{c} a_{11}x_1+\ldots+a_{1n}x_n = b_1\\ \ldots\\ a_{m1}x_1+\ldots+a_{mn}x_n = b_m\\ \end{array} \right. $$

Требуется определить, существует ли хотя бы один правильный столбец свободных членов при котором эта систсма совместна?

Отмечу, что решать и находить ничего не нужно. Нужен быстрый алгоритм выдающий true или false в зависимости от ответа на сформулированный вопрос. Хочется, чтобы этот алгоритм работал быстрее, чем простой перебор всех мыслимых правильных столбцов свободных членов (это очень долго).

Порядок чисел таков: $n\sim 100$, $m\sim 1000$, $\Delta_t\sim 30$.

Буду рад любым соображения и замечаниям.

[maxal]

Во-первых, если сумма $w_1+\ldots+w_s$ мала относительно $m$, то можно надеяться, что правильный столбец будет "коротким" в решетке натянутой на вектор-столбцы матрицы
$\left( \begin{matrix} a_{11} & \dots & a_{1n} & 2 & 0 & \dots & 0 \\ a_{21} & \dots & a_{2n} & 0 & 2 & \dots & 0 \\ \vdots\\ a_{m1} & \dots & a_{mn} & 0 & 0 & \dots & 2 \end{matrix}\right)$
и задача сводится к SVP (Shortest Vector Problem).

Если же пресловутая сумма немала, то можно свести задачу к CVP (Closest Vector Problem), заданной решеткой и вектором
$\left( \begin{matrix} a_{11} & \dots & a_{1n} & 2 & 0 & \dots & 0 \\ a_{21} & \dots & a_{2n} & 0 & 2 & \dots & 0 \\ \vdots\\ a_{m1} & \dots & a_{mn} & 0 & 0 & \dots & 2 \\ c_{11} & \dots & c_{1n} & c_{1n+1} & c_{1n+2} & \dots & c_{1n+m} \\ \vdots\\ c_{s1} & \dots & c_{sn} & c_{sn+1} & c_{sn+2} & \dots & c_{sn+m} \\ \end{matrix}\right)\left(\begin{matrix} 1/2\\ 1/2 \\ \vdots\\ 1/2\\ w_1 \\ \vdots \\ w_s \end{matrix}\right)$
где в матрице $(m+k)$-я строка (k=1,..,s) равна сумме строк с номерами $\Delta_1+\dots+\Delta_{k-1}+1, \dots, \Delta_k$ этой же матрицы.
Имеет смысл умножить последние s строк в матрице и s координат в векторе на большую константу, чтобы гарантировать выполнение равенств в этих строках.
Для целочисленности целевого вектора можно также умножить первые m строк/компонент на 2.

SVP и CVP можно решать с помощью алгоритма LLL, реализация которого есть, например, в библиотеке NTL.

[lofar]

Благодарю Вас, maxal. Это действительно здорово! Мои собственные рассуждения не выходили за рамки характеристики 2.

P. S. Меня заинтересовал вопрос терминологии. Прошу поправить если ошибаюсь. Всегда считал, что решетка это алгебраическая структура с операциями $\vee$ и $\wedge$. А решетка в Вашем определении похожа на дискретную подгруппу в $\mathbb R^n$.

[maxal]

lofar писал(а):

P. S. Меня заинтересовал вопрос терминологии. Прошу поправить если ошибаюсь. Всегда считал, что решетка это алгебраическая структура с операциями $\vee$ и $\wedge$. А решетка в Вашем определении похожа на дискретную подгруппу в $\mathbb R^n$.

Так и есть. Термин решетка (lattice) имеет несколько значений в математике. Здесь идет речь про вот такие решетки.

[lofar]

Уважаемый maxal.
Попытался реализовать предложенную Вами идею (мне подошел второй случай) и обнаружил следующую проблему. Алгоритм решения CVP из NTL работает только для полномерных решеток. Тогда как, решетка порожденная столбцами, указанной Вами матрицы, имеет размерность $m$ строго меньшую размерности пространства $m + s$. Скажите, пожалуйста, есть ли методы решения CVP для неполномерных решеток?

Насколько я понял, алгоритмы решения CVP полиномиальны, но находят лишь приближенное решение. CVP ---
NP-полная задача, поэтому ожидать лучшего не приходится. Тем не менее, существуют ли (экспоненциальные) оптимизированные алгоритмы точного решения CVP?

[lofar]

Первый вопрос снимаю, не подумав спросил. А про точное решение CVP интересно было бы узнать. Хочется воспользоваться готовым алгоритмом, если он есть конечно.

[maxal]

lofar писал(а):

Насколько я понял, алгоритмы решения CVP полиномиальны, но находят лишь приближенное решение.

Приближенное, но в конкретных теоретических пределах от настоящего. Кроме того, как правило, на практике LLL показывает гораздо лучшие результаты нежели те, что доказываются в теории; а в некоторых задачах, минимальный вектор оказывается настолько "короче" остальных, что LLL "вынужденно" находит именно его.

lofar писал(а):

CVP --- NP-полная задача, поэтому ожидать лучшего не приходится. Тем не менее, существуют ли (экспоненциальные) оптимизированные алгоритмы точного решения CVP?

Не знаю. Но с ходу могу предложить такой алгоритм: перебираем все целочисленные вектора а некоторой $\varepsilon$-окрестности целевого вектора и проверям их на принадлежность решетке (полиномиальным алгоритмом). Значение $\varepsilon$ можно считать равным длине разности между целевым вектором и вектором, полученным с помощью LLL.