Решение линейного диофантова уравнения приближенно

Рассмотрим следующую проблему:

Входные данные : гиперплоскость $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$ , задается вектором $\mathbf{a} \in \mathbb{Z}^n$ и $b \in \mathbb{Z}$ в стандартном двоичном представлении.

Выход : $\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

$d(\mathbf{x}, S)$$\mathbf{x} \in \mathbb{R}^n$$S \subseteq \mathbb{R}^n$$d(\mathbf{x}, S) = \min_{\mathbf{y} \in S}{\|\mathbf{x} - \mathbf{y}}\|_2$

Словом, нам дана гиперплоскость, и мы ищем точку в целочисленной решетке, которая является ближайшей к гиперплоскости.

Вопрос в том:

В чем сложность этой проблемы?

Обратите внимание, что полиномиальное время здесь будет означать полиномиальное значение в битах на входе. Насколько я вижу, проблема интересна даже в двух измерениях. Тогда нетрудно понять, что достаточно рассмотреть только те решения с но это суперполиномиально много вариантов.0 ≤ x 1 ≤ | 1 | / g c d ( a 1 , a 2$(x_1, x_2)$$0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$

Тесно связанной проблемой является решение линейного диофантового уравнения, то есть нахождение такого, что или определение, что такого не существует существует Таким образом, решение линейного диофантового уравнения эквивалентно определению, существует ли решение со значением 0 для задачи I, определенной выше. Линейное диофантово уравнение может быть решено за полиномиальное время; фактически даже системы линейных диофантовых уравнений могут быть решены за полиномиальное время путем вычисления нормальной формы матрицы Смита дающей систему. Существуют алгоритмы полиномиального времени, которые вычисляют нормальную форму Смита целочисленной матрицы, первый из которых определяетсяa T x = b $\mathbf{x} \in \mathbb{Z}^n$$\mathbf{a}^T\mathbf{x} = b$$\mathbf{x}$$\mathbf{A}$Каннан и Бачем .

Чтобы получить представление о линейных диофантовых уравнениях, мы можем снова рассмотреть двумерный случай. Ясно, что нет точного решения, если не делит . Если он делит , то вы можете запустить расширенный алгоритм GCD, чтобы получить два числа и такие что и установить и . Теперь вы можете увидеть, как приблизительная версия отличается: когда не делит , как мы можем найти целые числаb b s t a 1 s + a 2 t = g c d ( a 1 , a 2 ) x 1 = s b / g c d ( a 1 , a 2 ) x 2 = t b / g c d ( a 1$\mathsf{gcd}(a_1, a_2)$$b$$b$$s$$t$$a_1s + a_2t = \mathsf{gcd}(a_1, a_2)$$x_1 = sb/\mathsf{gcd}(a_1, a_2)$g c d ( a 1 , a 2 ) b x 1 , x $x_2 = tb/\mathsf{gcd}(a_1, a_2)$$\mathsf{gcd}(a_1, a_2)$$b$$x_1, x_2$такое, чтобы расстояние между и линией минимизировано?a 1 x 1 + a 2 x 2 = $(x_1, x_2)$$a_1x_1 + a_2x_2 =b$

Для меня эта проблема немного напоминает проблему ближайших векторов в решетках, но я не вижу очевидного перехода от одной проблемы к другой.

Хорошо, подумав об этом больше, я считаю, что у меня есть явное сокращение от этой проблемы до расширенного GCD; Я объясню это в случае , но я считаю, что оно распространяется на произвольное . Обратите внимание , что это находит свое , что сводит к минимуму расстояние до гиперплоскости, но не обязательно самого маленького (есть на самом деле бесконечно много значений , которые получают такое же минимальное расстояние) - Я считаю , что последняя задача также выполнимо, но еще не задумывался об этом. Алгоритм основан на нескольких простых принципах:n x $n=2$$n$ $\mathbf{x}$$\mathbf{x}$

• Если , то набор значений, принимаемых , точно ; кроме того, значения и с могут быть найдены эффективно (это в точности расширенный евклидов алгоритм).a ⋅ x = a 1 x 1 + a 2 x 2 $g=\mathrm{GCD}(a_1, a_2)$$\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$x 1 x 2 a 1 x 1 + а 2 х 2 = $\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$$x_1$$x_2$$a_1 x_1 + a_2 x_2 = g$
• Минимальное расстояние от гиперплоскости до точки на решетке - это минимальное расстояние от точки на решетке до гиперплоскости (очевидная, но полезная инверсия задачи).
• Расстояние от заданной точки до гиперплоскости пропорционально(в частности, это умноженное на это значение - но поскольку умножение всех расстояний на это значение не влияет на местоположение минимума, мы можем игнорировать нормирующий коэффициент).a ⋅ y = b | a ⋅ x - b | 1 / | а $\mathbf{x}$$\mathbf{a}\cdot\mathbf{y} = b$$\left|\mathbf{a}\cdot\mathbf{x}-b\right|$$1/|\mathbf{a}|$

Это предполагает следующую процедуру:

• Вычислите вместе с , чтобы .x $g=\mathrm{GCD}(a_1,a_2)$ a1x 0 1 +a2x 0 2 =$x^0_1, x^0_2$$a_1x^0_1+a_2x^0_2 = g$
• Вычислить и вычислить ; - (масштабированное) минимальное расстояние от решетки до гиперплоскости. Пусть будет либо либо ( , если не кратно ), в зависимости от того, какой из них достигает минимального расстояния.d=min(b-rg,(r+1)g-b)dsrr+1=⌈$r = \left\lfloor{b\over g}\right\rfloor$$d =\min(b-rg, (r+1)g-b)$$d$$s$$r$$r+1$b$=\left\lceil{b\over g}\right\rceil$$b$$g$
• Вычислить и ; затем является ближайшим кратным от до , и поэтомудостигает минимума этого расстояния по всем точкам решетки. x 2 = s x 0 2 a ⋅ x = s g g b | a ⋅ x - b $x_1 = sx^0_1$$x_2 = s x^0_2$$\mathbf{a}\cdot\mathbf{x} = sg$$g$$b$$\left|\mathbf{a}\cdot\mathbf{x}-b\right|$

Насколько я знаю, точно такая же процедура должна работать правильно в произвольных измерениях; ключ в том, что мерный GCD все еще удовлетворяет тождеству Безу, и поэтому, чтобы найти минимальное расстояние до точки решетки, вам нужно только найти ближайшее кратное от до .г $n$$g$$b$