złożoność największego wspólnego dzielnika (gcd)

33

Rozważ następujący problem zliczania (lub związany z tym problem decyzyjny): Biorąc pod uwagę dwie dodatnie liczby całkowite zakodowane w systemie binarnym, oblicz ich największy wspólny dzielnik (gcd). Jaka jest najmniejsza klasa złożoności, w której występuje ten problem? Czy możesz podać referencje?

W tym pytaniu nie interesują mnie przede wszystkim asymptotyczne granice czasu działania, ale raczej klasy złożoności. Czy problem dotyczy AC? Czy można udowodnić, że nie kłamie w AC0? Jakie są inne klasy złożoności w P, które są tutaj istotne?

cc.complexity-theory reference-request complexity-classes nt.number-theory Felix Breuer
źródło
3
@Joe: Moja interpretacja jest taka, że ​​pytający jest zainteresowany tym, czy język {(x, y, i) | i -ty ​​bit gcd (x, y) to 1} w NC, AC0 itd., ale przydatne byłoby wyjaśnienie pytającego.
Tsuyoshi Ito,
1
Tak, sformułowanie problemu decyzyjnego przez Tsuyoshi jest tym, co miałem na myśli - przepraszam za dwuznaczność. Proszę jednak nie koncentrować się na klasach złożoności, które zasugerowałem, ponieważ po prostu nie wiem, które klasy złożoności są tutaj istotne. Jestem ciekawy każdej nietrywialnej klasy złożoności, która jest podzbiorem P (lub FP, odpowiednio.), Która zawiera gcd.
Felix Breuer
1
Jestem ciekawy przypadku liczb całkowitych gaussowskich. Szybkie wyszukiwania w Google pokazują sposoby dostosowania normalnego algorytmu euklidesowego, ale żadne z nich nie omawia związku między liczbami naturalnymi a liczbami całkowitymi gaussa. Czy jakiś algorytm gcd nad liczbami naturalnymi daje nam algorytm nad liczbami całkowitymi Gaussa o tej samej złożoności? (Nie mam aplikacji, to czysta ciekawość.) Czy są też wydajne algorytmy randomizowane do obliczania GCD z krótszymi oczekiwanymi czasami działania?
Ross Snider,
1
Zobacz także cstheory.stackexchange.com/questions/2708/…
Zsbán Ambrus
1
Poprawiony link: mathoverflow.net/questions/44684/… . Dzięki za ostrzeżenie, Kaveh.
Zsbán Ambrus

Odpowiedzi:

44

Jest to główne otwarte pytanie w teorii złożoności: nie wiadomo, czy GCD można obliczyć w NC, i nie wiadomo, czy obliczenie GCD jest P-kompletne. Najlepsze równoległe algorytmy mają subliniowy równoległy czas działania, jeden z takich algorytmów wynika z Sorensona:

J. Sorenson. Dwa szybkie algorytmy GCD . Journal of Al Algorytmy, 1994.

Jeśli się nie mylę, nie wiadomo nawet, czy można zdecydować, czy dwie liczby całkowite są względnie pierwsze w NC.

John Watrous
źródło
Dziękuję, właśnie to chciałem wiedzieć! Jeśli jednak ktoś zna inne nietypowe podzbiory P, o których wiadomo, że zawierają gcd, daj mi znać.
Felix Breuer
15
Testowanie, czy dwie liczby całkowite są względnie pierwsze, jest również otwarte zgodnie z tym odniesieniem: Ograniczenia obliczeń równoległych , strona 231, problem B.5.7.
Robin Kothari,
4
Bardzo niedawne odniesienie to: Sorenson, Jonathan P. „Randomizowany algorytm GCD z równoległymi czasami równoległymi dla pamięci EREW PRAM.” Information Processing Letters 110, no. 5 (luty 2010 r.): 198–201. linkinghub.elsevier.com/retrieve/pii/S0020019009003640 .
Felix Breuer
3

Ten artykuł, opublikowany w 2007 roku, mówi, że liczba całkowita GCD jest w NC.

Edycja: twierdzenie jest prawdopodobnie fałszywe. Sprawdź komentarze.

Apoorv Gupta
źródło
4
Artykuł nigdy nie został opublikowany , został opublikowany tylko na stronie internetowej autora. Co więcej, sam autor nie uważa, że ​​jego praca z 2007 roku jest poprawna, ponieważ wymienia problem jako otwarty w swoich późniejszych pracach ( cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf ).
Emil Jeřábek wspiera Monikę
Nie wiedział tego. Dzięki za zwrócenie na to uwagi.
Apoorv Gupta
1
Nie sądzę, że tego rodzaju odpowiedzi powinny być zaniżone.
Alessandro Cosentino,