Komplexität des größten gemeinsamen Divisors (gcd)

33

Betrachten Sie das folgende Zählproblem (oder das damit verbundene Entscheidungsproblem): Berechnen Sie bei zwei binär codierten positiven Ganzzahlen ihren größten gemeinsamen Divisor (gcd). Was ist die kleinste Komplexitätsklasse, in der dieses Problem enthalten ist? Können Sie eine Referenz angeben?

In dieser Frage geht es mir nicht primär um asymptotische Grenzen der Laufzeit, sondern um Komplexitätsklassen. Liegt das Problem bei AC? Kann nachgewiesen werden, dass es nicht in AC0 liegt? Was sind andere Komplexitätsklassen in P, die hier relevant sind?

cc.complexity-theory reference-request complexity-classes nt.number-theory Felix Breuer
quelle
3
@ Joe: Meine Interpretation ist, dass der Fragesteller daran interessiert ist, ob die Sprache {(x, y, i) | Das i-te Bit von gcd (x, y) ist 1} in NC, AC0 usw., aber eine Klarstellung durch den Fragesteller wäre nützlich.
Tsuyoshi Ito
1
Ja, Tsuyoshi formuliert das Entscheidungsproblem so, wie ich es mir vorgestellt habe - entschuldige die Mehrdeutigkeit. Konzentrieren Sie sich jedoch nicht auf die von mir vorgeschlagenen Komplexitätsklassen, da ich einfach nicht weiß, welche Komplexitätsklassen hier relevant sind. Ich bin neugierig auf jede nichttriviale Komplexitätsklasse, die eine Teilmenge von P (bzw. FP) ist, die gcd enthält.
Felix Breuer
1
Ich bin neugierig auf den Fall von Gaußschen Ganzzahlen. Schnelle Google-Suche zeigt Möglichkeiten zur Anpassung des normalen euklidischen Algorithmus auf, aber keiner von ihnen diskutiert die Beziehung zwischen den natürlichen Zahlen und den Gaußschen Ganzzahlen. Gibt uns irgendein gcd-Algorithmus über die natürlichen Zahlen einen Algorithmus über die Gaußschen Ganzzahlen mit der gleichen Komplexität? (Ich habe keine Anwendung, das ist reine Neugier.) Gibt es auch effiziente randomisierte Algorithmen für die Berechnung von GCD mit geringeren erwarteten Laufzeiten?
Ross Snider
1
Siehe auch cstheory.stackexchange.com/questions/2708/…
Zsbán Ambrus
1
Korrigierter Link: mathoverflow.net/questions/44684/… . Danke für die Warnung, Kaveh.
Zsbán Ambrus

Antworten:

44

Dies ist eine wichtige offene Frage in der Komplexitätstheorie: Es ist nicht bekannt, ob GCDs in NC berechnet werden können, und es ist nicht bekannt, ob die Berechnung von GCDs P-vollständig ist. Die besten parallelen Algorithmen haben eine sublineare parallele Laufzeit, wobei ein solcher Algorithmus auf Sorenson zurückzuführen ist:

J. Sorenson. Zwei schnelle GCD-Algorithmen . Journal of Algorithms, 1994.

Wenn ich mich nicht irre, ist nicht einmal bekannt, ob man in NC entscheiden kann, ob zwei ganze Zahlen relativ prim sind.

John Watrous
quelle
Danke, das wollte ich wissen! Wenn jemand jedoch andere nichttriviale Untergruppen von P kennt, von denen bekannt ist, dass sie gcd enthalten, lassen Sie es mich bitte wissen.
Felix Breuer
15
Die Prüfung, ob zwei Ganzzahlen relativ prim sind, ist auch gemäß dieser Referenz offen: Grenzen der parallelen Berechnung , Seite 231, Problem B.5.7.
Robin Kothari
4
Eine sehr aktuelle Literaturstelle ist: Sorenson, Jonathan P. "Ein randomisierter, zeitparalleler GCD-Algorithmus für den EREW-PRAM." Information Processing Letters 110, No. 5 (Februar 2010): 198-201. linkedhub.elsevier.com/retrieve/pii/S0020019009003640 .
Felix Breuer
3

In diesem 2007 veröffentlichten Artikel heißt es, dass die Ganzzahl GCD in NC vorliegt.

Edit: Die Behauptung ist wahrscheinlich falsch. Überprüfen Sie die Kommentare.

Apoorv Gupta
quelle
4
Der Artikel wurde nie veröffentlicht , sondern nur auf der Website des Autors veröffentlicht. Darüber hinaus scheint der Autor selbst nicht zu glauben, dass seine Arbeit von 2007 korrekt ist, da er das Problem in seinen späteren Arbeiten als offen aufführt ( cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf ).
Emil Jeřábek unterstützt Monica
Wusste ich nicht. Vielen Dank für den Hinweis.
Apoorv Gupta
1
Ich denke nicht, dass diese Art von Antworten herabgestimmt werden sollte.
Alessandro Cosentino