Rozważ następujący problem:
Dane wejściowe : hiperpłaszczyzna H = { y ∈ R n : a T y = b }
Wyjście : x ∈ Z n = arg min d ( 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 )
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 )
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 A
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)
Problem dla mnie brzmi trochę jak najbliższy problem wektorowy w sieciach, ale nie widzę wyraźnej redukcji z jednego problemu do drugiego.
źródło
Odpowiedzi:
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 x x
Sugeruje to następującą procedurę:
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 .
źródło