¿Existe un algoritmo logarítmico para la divisibilidad?

Question

¿Existe un algoritmo para comprobar la divisibilidad en el espacio $O(\log n)$ o incluso en el espacio $O(\log(n)^k)$ para algunos $k$ ? Dado un par de enteros $(a, b)$ el algoritmo debe devolver TRUE si $b$ es divisible por $a$ y FALSE en caso contrario. Entiendo que no hay pruebas de que la divisibilidad sea no en $L$ ya que eso implicaría $P \ne L$ que está abierto. También entiendo que si hay un algoritmo no determinista en $O(\log(n)^k)$ entonces hay un algoritmo determinista en $O(\log(n)^{2k})$ por el teorema de Savitch. Creo que he descubierto una $L$ algoritmo para verificar $a*b=c$ y también un $FL$ algoritmo para calcular $c$ (esencialmente el método que me enseñaron en la escuela primaria, reutilizando la tinta cuando es posible), pero no he podido adaptarlo a la divisibilidad. ¿Se conoce un algoritmo de este tipo para la divisibilidad?

Answer 1

(Esta es una versión actualizada de mi comentario sobre la pregunta).

Beame, Cook y Hoover [BCH86] demostraron que la divisibilidad de los enteros es en L. Más recientemente, Chiu, Davida y Litow [CDL01] demostraron que los enteros división también está en L.

Referencias

BCH86] Paul W. Beame, Stephen A. Cook y H. James Hoover. Circuitos de profundidad de registro para la división y problemas relacionados. SIAM Journal on Computing , 15(4):994-1003, nov. 1986. DOI: 10.1137/0215070

CDL01] Andrew Chiu, George Davida y Bruce Litow. División en logspace-uniform NC 1 . Informática teórica y aplicaciones , 35(3):259-275, mayo de 2001. DOI: 10.1051/ita:2001119 .

Answer 2

Editado para añadir: Como señala Gadi en un comentario, esta respuesta es errónea.

Si tiene un algoritmo logspace para verificar $x \times y = z$ entonces, como no te preocupa el tiempo de ejecución, puedes simplemente comprobar, para todos $c$ con $1 < c \le b$ , ya sea $a \times c = b$ .