complexité du plus grand commun diviseur (gcd)

Considérez le problème de comptage suivant (ou le problème de décision associé): Étant donné deux entiers positifs codés en binaire, calculez leur plus grand commun diviseur (gcd). Quelle est la plus petite classe de complexité dans laquelle ce problème est contenu? Pouvez-vous fournir une référence?

Dans cette question, je ne m'intéresse pas principalement aux limites asymptotiques du temps d'exécution, mais plutôt aux classes de complexité. Le problème est en AC? Peut-on prouver qu'il ne ment pas en AC0? Quelles sont les autres classes de complexité à l'intérieur de P qui sont pertinentes ici?

cc.complexity-theory reference-request complexity-classes nt.number-theory Felix Breuer
la source

@ Joe: Mon interprétation est que le demandeur est intéressé à savoir si la langue {(x, y, i) | le i-ème bit de gcd (x, y) est 1} est dans NC, AC0, etc., mais une clarification par le demandeur serait utile.

Tsuyoshi Ito

Oui, le libellé de Tsuyoshi sur le problème de la décision est ce que j'avais en tête - désolé pour l'ambiguïté. Cependant, veuillez ne pas vous concentrer sur les classes de complexité que j'ai suggérées, car je ne sais tout simplement pas quelles classes de complexité sont pertinentes ici. Je suis curieux de savoir quelle classe de complexité non triviale est un sous-ensemble de P (ou FP, resp.) Contenant gcd.

Felix Breuer

Je suis curieux du cas des nombres entiers gaussiens. Les recherches Google rapides montrent des moyens d’adapter l’algorithme euclidien normal, mais aucune d’entre elles ne discute de la relation entre les nombres naturels et les entiers gaussiens. Un algorithme gcd sur les nombres naturels nous donne-t-il un algorithme sur les entiers gaussiens avec la même complexité? (Je n'ai pas d'application, c'est de la pure curiosité.) En outre, existe-t-il des algorithmes efficaces randomisés pour calculer GCD avec des durées de fonctionnement inférieures?

Ross Snider

Voir aussi cstheory.stackexchange.com/questions/2708/…

Zsbán Ambrus Le

Lien corrigé: mathoverflow.net/questions/44684/… . Merci pour l'avertissement, Kaveh.

Zsbán Ambrus

Réponses:

C'est une question ouverte majeure dans la théorie de la complexité: on ne sait pas si les GCD peuvent être calculés en NC et on ne sait pas si le calcul des GCD est P-complet. Les meilleurs algorithmes parallèles ont un temps d'exécution parallèle sub-linéaire, l'un de ces algorithmes étant dû à Sorenson:

J. Sorenson. Deux algorithmes GCD rapides . Journal of Algorithms, 1994.

Si je ne me trompe pas, on ne sait même pas si on peut décider si deux entiers sont relativement premiers dans NC.

John Watrous
la source

Merci, c'est ce que je voulais savoir! Toutefois, si quelqu'un connaît d'autres sous-ensembles non triviaux de P connus pour contenir gcd, veuillez me le faire savoir.

Felix Breuer

Selon cette référence, il est également ouvert de vérifier si deux entiers sont relativement premiers: Limites au calcul parallèle , page 231, problème B.5.7.

Robin Kothari

Une référence très récente est: Sorenson, Jonathan P. «Un algorithme de GCD parallèle temporel sous-linéarisé aléatoire pour EREW PRAM.» Information Processing Letters 110, no. 5 (février 2010): 198-201. linkhub.elsevier.com/retrieve/pii/S0020019009003640 .

Felix Breuer

Un peu tard dans la journée mais l' article suivant de Allender, Saks, Shparlinski prouve que (parmi d'autres bornes inférieures) que GCD n'est pas dans ou pour tout prime . $\mathsf{AC}^0$ $\mathsf{AC}^0[p]$ $p$

SamiD
la source

Voir aussi: cstheory.stackexchange.com/questions/8000/…

SamiD

Cet article, publié en 2007, dit que GCD entier est en NC.

Edit: L'assertion est probablement fausse. Vérifiez les commentaires.

Apoorv Gupta
la source

Le document n'a jamais été publié , il n'a été affiché que sur le site Web de l'auteur. De plus, l'auteur lui - même ne semble pas croire que son article de 2007 soit correct, car il a énuméré le problème dans ses articles ultérieurs ( cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf ).

Emil Jeřábek soutient Monica

Ne savais pas ça. Merci de l'avoir signalé.

Apoorv Gupta

Je ne pense pas que ce genre de réponses devrait être voté.

Alessandro Cosentino