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?
Is there a log-space algorithm for divisibility?
-
0Isn't the euclidean algorithm log space and with the identity $a | b$ iff $\gcd(a,b)=a$, wouldn't this give you a logspace algorithm? – 2011-10-25
-
1If so, yes, but I don't know how to make the Euclidean algorithm log-space either. The way I would ordinarily implement it is O(n) space. Note that n ~ log(b) here, so log-space means O(log(log(b))) space. – 2011-10-25
-
1The euclidean algorithm is most certainly an overkill; if b divides a, it will be discovered in the first step of the algorithm (where we divide a by b and take the remainder)... – 2011-10-25
-
0I'm not very familiar with complexity theory, but determining divisibility without examining all of the digits does not sound plausible to me... is there intuition for why such an algorithm might exist? – 2011-10-25
-
1@user7530, all the digits can be examined, they just can't be copied into working space at the same time. See http://en.wikipedia.org/wiki/L_(complexity%29. My intuition is that divisibility is in P and P=L might be true, and also it seems like an easy P problem compared to others. – 2011-10-25
-
0@Dan: I hadn't encountered $L$ before, so I don't know the definition and the Wikipedia article doesn't really provide one -- "a logarithmic amount of memory space" is rather vague. Am I right in thinking that the definition of space complexity given on slide 2 of [these slides](http://homepage.cs.uri.edu/faculty/hamel/courses/2011/spring2011/csc544/lecture-notes/18-space-complexity.pdf) isn't the one to be applied here? If it were, the class $L$ would be rather boring, since the output couldn't depend on most of the input. Perhaps the Wikipedia article should be clarified? – 2011-10-25
-
1Integer division is known to be in L. Page 22 of the slides “[My Favorite Ten Complexity Theorems of the Past Decade II](http://www.cs.uchicago.edu/~fortnow/talks/favorite2.ppt)” by Lance Fortnow refers to Chiu 1995, although I cannot locate this reference right now. If you can access [Chiu, Davida, and Litow 2001](http://dx.doi.org/10.1051/ita%3A2001119), I am sure that it contains the reference to it. – 2011-10-25
-
0@Tsuyoshi: You could write that as an answer. – 2011-10-25
-
0If you are allowed to overwrite the contents of $b$, you can just subtract $a$ from $b$ repeatedly until you get zero or a negative number. – 2011-10-25
-
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
(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.
-
1By the way, according to the introduction of [BCH86], there seems to be a folklore O((log n)^2)-space algorithm. – 2011-10-26
-
2I realized that the [master thesis of Chiu](http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.38.6264&rep=rep1&type=pdf) in 1995 seems to contain a proof that integer division is in L (and more strongly in log-space-uniform NC1), and I am not sure its relation to [CDL01] because I cannot access [CDL01]. – 2011-10-26
-
1Even more is true, we know that [it is in uniform $TC^0$](http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.15.8882). – 2011-11-02
-
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
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$.
-
2I 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