complexidade do maior divisor comum (MDC)

33

Considere o seguinte problema de contagem (ou o problema de decisão associado): Dados dois inteiros positivos codificados em binário, calcule seu maior divisor comum (MDC). Qual é a menor classe de complexidade em que esse problema está contido? Você pode fornecer uma referência?

Nesta questão, não estou interessado principalmente em limites assintóticos no tempo de execução, mas em classes de complexidade. O problema está no AC? Pode-se provar que não está no AC0? Quais são as outras classes de complexidade dentro de P que são relevantes aqui?

cc.complexity-theory reference-request complexity-classes nt.number-theory Felix Breuer
fonte
3
@ Joe: Minha interpretação é que o solicitante está interessado em saber se o idioma {(x, y, i) | o i-ésimo bit de gcd (x, y) é 1} está em NC, AC0, etc., mas um esclarecimento pelo solicitante seria útil.
Tsuyoshi Ito
1
Sim, a formulação de Tsuyoshi do problema de decisão é o que eu tinha em mente - desculpe pela ambiguidade. No entanto, não se concentre nas classes de complexidade que sugeri, pois simplesmente não sei quais classes de complexidade são relevantes aqui. Estou curioso sobre qualquer classe de complexidade não trivial que seja um subconjunto de P (ou FP, resp.) Que contenha gcd.
Felix Breuer #
1
Estou curioso sobre o caso de números inteiros gaussianos. As pesquisas rápidas no Google mostram maneiras de adaptar o algoritmo euclidiano normal, mas nenhuma delas discute a relação entre os números naturais e os números inteiros gaussianos. Algum algoritmo gcd sobre os números naturais nos fornece um algoritmo sobre os números inteiros gaussianos com a mesma complexidade? (Não tenho aplicativo, isso é pura curiosidade.) Além disso, existem algoritmos aleatórios eficientes para calcular o GCD com tempos de execução esperados mais baixos?
precisa
1
Veja também cstheory.stackexchange.com/questions/2708/…
Zsbán Ambrus
1
Link corrigido: mathoverflow.net/questions/44684/… . Obrigado pelo aviso, Kaveh.
Zsbán Ambrus

Respostas:

44

Essa é uma questão importante em aberto na teoria da complexidade: não se sabe se os GCDs podem ser computados na NC e não se sabe se os GCDs de computação estão completos em P. Os melhores algoritmos paralelos têm tempo de execução paralelo sub-linear, sendo um deles devido a Sorenson:

J. Sorenson. Dois algoritmos GCD rápidos . Journal of Algorithms, 1994.

Se não me engano, nem se sabe se é possível decidir se dois números inteiros são relativamente primos no NC.

John Watrous
fonte
Obrigado, é isso que eu queria saber! No entanto, se alguém conhece outros subconjuntos não triviais de P que são conhecidos por conter gcd, entre em contato.
Felix Breuer #
15
Testar se dois números inteiros são relativamente primos também é aberto de acordo com esta referência: Limites para computação paralela , página 231, problema B.5.7.
precisa
4
Uma referência muito recente é: Sorenson, Jonathan P. "Um algoritmo GCD paralelo no tempo sublinear aleatório para o EREW PRAM". Information Processing Letters 110, no. 5 (fevereiro de 2010): 198-201. bindinghub.elsevier.com/retrieve/pii/S0020019009003640 .
Felix Breuer
3

Este artigo, publicado em 2007, diz que o GCD inteiro está no NC.

Edit: A afirmação é provavelmente falsa. Verifique os comentários.

Apoorv Gupta
fonte
4
O artigo nunca foi publicado , foi publicado apenas no site do autor. Além disso, o próprio autor não parece acreditar que seu artigo de 2007 esteja correto, pois lista o problema como aberto em seus artigos posteriores ( cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf ).
Emil Jeřábek apoia Monica
Não sabia isso. Obrigado por apontar isso.
Apoorv Gupta
1
Eu não acho que esse tipo de resposta deva ser rebaixado.
Alessandro Cosentino 05/09