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

15

Rozważ następujący problem:

Dane wejściowe : hiperpłaszczyzna H = { yR n : a T y = b }H={yRn:aTy=b} , podana przez wektor aZ naZn i b ZbZ w standardowej reprezentacji binarnej.

Wyjście : xZ n = arg min d ( x , H )xZn=argmind(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 ( x , S ) d(x,S)xR nxRn S R nSRn d ( x , S ) = min ySx - y2d(x,S)=minySxy2

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 )(x1,x2) z 0 x 1| a 1 | / g c d ( a 1 , a 2 )0x1|a1|/gcd(a1,a2) 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ą przezxZ n a T x = b x AxZnaTx=bxAKannan 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łkowitegcd(a1,a2)gcd(a1,a2)bbbbsstta1s+a2t=gcd(a1,a2)a1s+a2t=gcd(a1,a2)x1=sb/gcd(a1,a2)x1=sb/gcd(a1,a2)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 = bx2=tb/gcd(a1,a2)gcd(a1,a2)bx1,x2tak że odległość między a linią jest zminimalizowana?(x1,x2)a1x1+a2x2=b

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

Sasho Nikolov
źródło
nie, nie robi: zbliżenie diofantyny to inny problem niż rozwiązanie równania diofantyny. w problemie z aproksymacją diofantyny otrzymujesz n liczb rzeczywistych i chcesz pomnożyć je wszystkie przez jedną liczbę całkowitą Q , aby wszystkie znajdowały się w zakresie ϵ od jakiejś liczby całkowitej. problemem jest znalezienie optymalnego kompromisu między wielkością Q a ϵ . Nie widzę związku między moim problemem a tym. nQϵQϵ
Sasho Nikolov,
Jaki jest twój format wejściowy? Wydaje się, że jeśli dwie wartości współrzędnych są niewspółmierne to minimalna ten wynosi zero (przecinają się z odpowiednią płaszczyzną 2-wymiarowe, aby równanie POSTAĆ s x + t y = w o s i t niewspółmiernego tj α sasx+ty=wstt irracjonalne, a następnie użyj standardowych wyników na{nα}αst( mod1 ), aby pokazać, że linia przebiega arbitralnie blisko punktów sieci. {nα}(mod1)
Steven Stadnicki
W szczególności oznacza to, że twoja „min” powinna być „inf” (sinus przejmujesz nieskończenie wiele punktów), a problem, czy i n f d ( x , H ) = 0,  różni się od pytania czy istnieje jakieś x z d ( x , H ) = 0 . Oznacza to, że współczynniki a muszą być liczbami wymiernymi, aby problem miał nietrywialne rozwiązanie, a następnie wydaje się, że problem przybiera postać bardzo euklidesową, ściśle powiązaną z wielowymiarowymi algorytmami GCD. Czy coś brakuje? inf d(x,H)=0xd(x,H)=0a
Steven Stadnicki
@StevenStadnicki prawo. można założyć, aZ n i b Z. (dodam, że na pytanie, muszę pominięcia go). dane wejściowe podano w standardowej reprezentacji binarnej. pytanie jest interesujące, nawet gdy n = 2 . wystarczy rozważyć wszystkie możliwe rozwiązania ( x 1 , x 2 ) z x 1| a 1 | / g c d ( a 1 , a 2 )aZnbZn=2(x1,x2)x1|a1|/gcd(a1,a2), Ale poszukiwanie bruteforce będzie superpolynomial w binarnej reprezentacji w 1 , 2 . a1,a2
Sasho Nikolov

Odpowiedzi:

5

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=2n xx

  • Jeśli g = G C D ( a 1 , a 2 ) , to zestaw wartości przyjmowanych przez ax = 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 1g=GCD(a1,a2)ax=a1x1+a2x2{0,±g,±2g,±3g,}x1x2+ 2 x 2 = g można skutecznie stwierdzono (to jest dokładnie rozszerzony algorytm euklidesowa).a1x1+a2x2=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 ay = b jest proporcjonalna do | ax - 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).xay=b|axb|1/|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=GCD(a1,a2)x01,x02
  • Oblicz r = bgi obliczyćd=min(b-rg,(r+1)g-b); djest (skalowaną) minimalną odległością od sieci do hiperpłaszczyzny. NiechabyćRlubR+1(=bg, chyba żebjest wielokrotnościąg) w zależności od tego, który z nich osiąga minimalną odległość.
  • Oblicz x 1 = s x 0 1 i x 2 = s x 0 2 ; wtedy ax = s g jest najbliższą wielokrotnością g do b , a zatem | ax - b | osiąga minimum tej odległości we wszystkich punktach sieci.

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 .

Steven Stadnicki
źródło