complejidad del máximo divisor común (mcd)

33

Considere el siguiente problema de conteo (o el problema de decisión asociado): dados dos enteros positivos codificados en binario, calcule su máximo divisor común (mcd). ¿Cuál es la clase de complejidad más pequeña en la que se encuentra este problema? ¿Me puede proporcionar una referencia?

En esta pregunta, no estoy interesado principalmente en los límites asintóticos del tiempo de ejecución, sino en las clases de complejidad. ¿El problema está en AC? ¿Se puede demostrar que no miente en AC0? ¿Cuáles son otras clases de complejidad dentro de P que son relevantes aquí?

cc.complexity-theory reference-request complexity-classes nt.number-theory Felix Breuer
fuente
3
@ Joe: Mi interpretación es que el autor de la pregunta está interesado en saber si el lenguaje {(x, y, i) | el i-ésimo bit de mcd (x, y) es 1} está en NC, AC0, etc., pero sería útil una aclaración del autor de la pregunta.
Tsuyoshi Ito
1
Sí, la formulación de Tsuyoshi del problema de decisión es lo que tenía en mente, perdón por la ambigüedad. Sin embargo, no se centre en las clases de complejidad que sugerí, ya que simplemente no sé qué clases de complejidad son relevantes aquí. Tengo curiosidad sobre cualquier clase de complejidad no trivial que sea un subconjunto de P (o FP, resp.) Que contenga gcd.
Felix Breuer el
1
Tengo curiosidad sobre el caso de los enteros gaussianos. Las búsquedas rápidas en Google muestran formas de adaptar el algoritmo euclidiano normal, pero ninguna de ellas discute la relación entre los números naturales y los enteros gaussianos. ¿Algún algoritmo gcd sobre los números naturales nos da un algoritmo sobre los enteros gaussianos con la misma complejidad? (No tengo una aplicación, esto es pura curiosidad). Además, ¿existen algoritmos aleatorizados eficientes para calcular GCD con tiempos de ejecución esperados más bajos?
Ross Snider
1
Ver también cstheory.stackexchange.com/questions/2708/…
Zsbán Ambrus
1
Enlace corregido: mathoverflow.net/questions/44684/… . Gracias por la advertencia, Kaveh.
Zsbán Ambrus

Respuestas:

44

Esta es una pregunta abierta importante en la teoría de la complejidad: no se sabe si los GCD se pueden calcular en NC, y no se sabe si calcular los GCD es P-completo. Los mejores algoritmos paralelos tienen un tiempo de ejecución paralelo sublineal, uno de los cuales se debe a Sorenson:

J. Sorenson. Dos algoritmos GCD rápidos . Revista de Algoritmos, 1994.

Si no me equivoco, ni siquiera se sabe si uno puede decidir si dos enteros son relativamente primos en Carolina del Norte.

John Watrous
fuente
¡Gracias, eso es lo que quería saber! Sin embargo, si alguien conoce otros subconjuntos no triviales de P que se sabe que contienen mcd, hágamelo saber.
Felix Breuer el
15
La prueba de si dos enteros son relativamente primos también está abierta de acuerdo con esta referencia: límites al cálculo paralelo , página 231, problema B.5.7.
Robin Kothari el
44
Una referencia muy reciente es: Sorenson, Jonathan P. "Un algoritmo GCD paralelo al tiempo sublineal aleatorio para el EREW PRAM". Information Processing Letters 110, no. 5 (febrero de 2010): 198-201. enlacehub.elsevier.com/retrieve/pii/S0020019009003640 .
Felix Breuer el
3

Este documento, publicado en 2007, dice que el entero GCD está en Carolina del Norte.

Editar: La afirmación es probablemente falsa. Revisa los comentarios.

Apoorv Gupta
fuente
44
El artículo nunca se publicó , solo se publicó en el sitio web del autor. Además, el propio autor no parece creer que su documento de 2007 sea correcto, ya que enumera el problema como abierto en sus documentos posteriores ( cs.cornell.edu/courses/CS6820/2012sp/Handouts/Sedjelmaci09.pdf ).
Emil Jeřábek apoya a Monica el
No sabía eso. Gracias por mencionarlo.
Apoorv Gupta
1
No creo que este tipo de respuestas deba ser rechazado.
Alessandro Cosentino