6
$\begingroup$

Is there an algorithm to test divisibility in space $O(\log n)$, or even in space $O(\log(n)^k)$ for some $k$? Given a pair of integers $(a, b)$, the algorithm should return TRUE if $b$ is divisible by $a$, and FALSE otherwise. I understand that there is no proof that divisibility is not in $L$ since that would imply $P \ne L$ which is open. Also I understand that if there is a nondeterministic algorithm in $O(\log(n)^k)$ then there is a deterministic algorithm in $O(\log(n)^{2k})$, by Savitch's theorem. I believe I've figured out an $L$ algorithm to verify $a*b=c$, and also an $FL$ algorithm to compute $c$ (essentially the method I was taught in grade school, reusing ink when possible), but I haven't been able to adapt it to divisibility. Is such an algorithm for divisibility known?

  • 0
    @TonyK, the model does not permit overwriting the input. You can imagine an "input tape" containing the input, and$a$separate "work tape" (which, in this problem, is supposed to be logarithmic in input size). You may, of course, copy down parts of the input, but you need to "pay" for that.2011-10-25

2 Answers 2

7

(This is an updated version of my comment on the question.)

Beame, Cook, and Hoover [BCH86] showed that integer divisibility is in L. More recently, Chiu, Davida, and Litow [CDL01] showed that integer division is also in L.

References

[BCH86] Paul W. Beame, Stephen A. Cook, and H. James Hoover. Log depth circuits for division and related problems. SIAM Journal on Computing, 15(4):994–1003, Nov. 1986. DOI: 10.1137/0215070

[CDL01] Andrew Chiu, George Davida, and Bruce Litow. Division in logspace-uniform NC1. Theoretical Informatics and Applications, 35(3):259–275, May 2001. DOI: 10.1051/ita:2001119.

  • 1
    @Kaveh: That is true. I did not mention that result in the answer because I wanted to keep the answer simple by focusing on space complexity by a Turing machine.2011-11-10
0

Edited to add: As Gadi points out in a comment, this answer is wrong.

If you have a logspace algorithm to verify $x \times y = z$, then since you're not concerned with running time, you can simply check, for all $c$ with $1 < c \le b$, whether $a \times c = b$.

  • 2
    I believe he meant that the algorithm is logspace in the sum of lengths of x,y,z. What you suggest is not logspace since writing c takes up space on the work tape.2011-10-25