Rozwiązanie w przybliżeniu liniowego równania diofantyny

Rozważ następujący problem:

Dane wejściowe : hiperpłaszczyzna $H = \{ \mathbf{y} \in \mathbb{R}^n: \mathbf{a}^T\mathbf{y} = {b}\}$ , podana przez wektor $\mathbf{a} \in \mathbb{Z}^n$ i $b \in \mathbb{Z}$ w standardowej reprezentacji binarnej.

Wyjście : $\mathbf{x} \in \mathbb{Z}^n = \arg \min d( \mathbf{x}, H)$

W powyższej notacji dla a jest zdefiniowany jako , tj. Jest to naturalna odległość euklidesowa między zestawem punktów a pojedynczym punktem .$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$

Innymi słowy, otrzymujemy hiperpłaszczyznę i szukamy punktu w sieci liczb całkowitych najbliższego hiperpłaszczyźnie.

Pytanie brzmi:

Jaka jest złożoność tego problemu?

Zauważ, że tutaj czas wielomianowy będzie oznaczał wielomian w bitowej wielkości danych wejściowych. Z tego co widzę problem jest interesujący nawet w dwóch wymiarach. Wtedy nietrudno dostrzec, że wystarczy wziąć pod uwagę tylko te rozwiązania $(x_1, x_2)$ z $0\leq x_1 \leq |a_1|/\mathsf{gcd}(a_1, a_2)$ ale to jest wielobiegunowo wiele opcji.

Blisko spokrewnionym problemem jest rozwiązanie liniowego równania diofantyny, tj. Znalezienie takiego, że lub ustalenie, że nie ma takiego istnieje. Zatem rozwiązanie liniowego równania diofantyny jest równoznaczne z ustaleniem, czy istnieje rozwiązanie wartości 0 dla problemu, który zdefiniowałem powyżej. Liniowe równanie diofantyczne można rozwiązać w czasie wielomianowym; w rzeczywistości nawet układy liniowych równań diofantycznych można rozwiązać w czasie wielomianowym, obliczając normalną postać Smitha macierzy daje układ. Istnieją wielomianowe algorytmy czasowe, które obliczają normalną postać Smitha macierzy liczb całkowitych, pierwszą podaną przezx ∈ Z n a T x = b x $\mathbf{x} \in \mathbb{Z}^n$$\mathbf{a}^T\mathbf{x} = b$$\mathbf{x}$$\mathbf{A}$Kannan i Bachem .

Aby uzyskać intuicję na temat liniowych równań diofantycznych, możemy ponownie rozważyć przypadek dwuwymiarowy. Oczywiście nie ma dokładnego rozwiązania, jeśli nie dzieli . Jeśli dzieli , możesz uruchomić rozszerzony algorytm GCD, aby uzyskać dwie liczby i tak, że i ustaw i . Teraz możesz zobaczyć, jak różni się wersja przybliżona: kiedy nie dzieli , jak znaleźć liczby całkowite$\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)$x2=tb/gcd(a1,a 2 ) g c d ( a 1 , a 2 ) b x 1 , x 2 ( x 1 , x 2 ) a 1 x 1 + a 2 x 2 = $x_2 = tb/\mathsf{gcd}(a_1, a_2)$$\mathsf{gcd}(a_1, a_2)$$b$$x_1, x_2$tak że odległość między a linią jest zminimalizowana?$(x_1, x_2)$$a_1x_1 + a_2x_2 =b$

Problem dla mnie brzmi trochę jak najbliższy problem wektorowy w sieciach, ale nie widzę wyraźnej redukcji z jednego problemu do drugiego.

W porządku, myśląc o tym więcej, uważam, że mam wyraźną redukcję tego problemu do rozszerzonego GCD; Wyjaśnię to w przypadku n = 2 , ale wierzę, że rozciąga się na dowolne n . Zauważ, że znajduje to x, który minimalizuje odległość do hiperpłaszczyzny, ale niekoniecznie najmniejszy x (w rzeczywistości istnieje nieskończenie wiele wartości, które osiągają tę samą minimalną odległość) - uważam, że ten drugi problem jest również wykonalny, ale nie dał jakakolwiek prawdziwa myśl. Algorytm opiera się na kilku prostych zasadach:$n=2$$n$ $\mathbf{x}$$\mathbf{x}$

• Jeśli g = G C D ( a 1 , a 2 ) , to zestaw wartości przyjmowanych przez a ⋅ x = a 1 x 1 + a 2 x 2 wynosi dokładnie { 0 , ± g , ± 2 g , ± 3 g , … } ; Ponadto wartości x 1, i x 2 z a 1 x $g=\mathrm{GCD}(a_1, a_2)$$\mathbf{a}\cdot\mathbf{x} = a_1 x_1 + a_2 x_2$$\left\{0, \pm g, \pm 2g, \pm 3g, \ldots\right\}$$x_1$$x_2$+ 2 x 2 = g można skutecznie stwierdzono (to jest dokładnie rozszerzony algorytm euklidesowa).$a_1 x_1 + a_2 x_2 = g$
• Minimalna odległość od hiperpłaszczyzny do punktu na sieci to minimalna odległość od punktu na sieci do hiperpłaszczyzny (oczywiste, ale użyteczne odwrócenie problemu).
• Odległość od danego punktu x do hiperpłaszczyzny a ⋅ y = b jest proporcjonalna do | a ⋅ x - b | (konkretnie, jest to 1 / | a | razy ta wartość - ale ponieważ pomnożenie wszystkich odległości przez tę wartość nie ma wpływu na lokalizację minimum, możemy zignorować współczynnik normalizujący).$\mathbf{x}$$\mathbf{a}\cdot\mathbf{y} = b$$\left|\mathbf{a}\cdot\mathbf{x}-b\right|$$1/|\mathbf{a}|$

Sugeruje to następującą procedurę:

• Oblicz g = G C D ( a 1 , a 2 ) , wraz z x 0 1 , x 0 2 tak, że a 1 x 0 1 + a 2 x 0 2 = g .$g=\mathrm{GCD}(a_1,a_2)$$x^0_1, x^0_2$$a_1x^0_1+a_2x^0_2 = g$
• Oblicz r = ⌊ bg ⌋i obliczyćd=min(b-rg,(r+1)g-b); djest (skalowaną) minimalną odległością od sieci do hiperpłaszczyzny. NiechabyćRlubR+1(=⌈$r = \left\lfloor{b\over g}\right\rfloor$$d =\min(b-rg, (r+1)g-b)$$d$$s$$r$$r+1$g ⌉, chyba żebjest wielokrotnościąg) w zależności od tego, który z nich osiąga minimalną odległość.$=\left\lceil{b\over g}\right\rceil$$b$$g$
• Oblicz x 1 = s x 0 1 i x 2 = s x 0 2 ; wtedy a ⋅ x = s g jest najbliższą wielokrotnością g do b , a zatem | a ⋅ x - b | osiąga minimum tej odległości we wszystkich punktach sieci.$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|$

O ile mi wiadomo, dokładnie ta sama procedura powinna działać poprawnie w dowolnych wymiarach; kluczem jest to, że n- wymiarowy GCD nadal spełnia tożsamość Bezouta, więc aby znaleźć minimalną odległość do punktu sieci, wystarczy znaleźć najbliższą wielokrotność g do b .$n$$g$$b$