# Edit distance in sublinear space

What is the best known complexity for computing the exact edit distance between two strings of the same length using working space which is sublinear in the size of the input? I assume the input is stored in some read-only format. Is this a previously studied problem?

To make the question a little more specific, how about $\Theta(\sqrt{n})$ space where $n$ is the length of each input string.

Edit. Following the answer of David Eppstein, it seems a good question is simply if the edit distance can be found in polynomial time and $\Theta(\sqrt{n})$ space. Any lower bounds would also be interesting.

• Regarding the edit: I think you misunderstand something. David Eppstein’s answer shows the problem is solvable in NL, hence also in P. – Emil Jeřábek supports Monica Aug 17 '14 at 22:42
• ... Actually, the original Wagner–Fischer algorithm already does that. – Emil Jeřábek supports Monica Aug 17 '14 at 22:54
• I assume the edited version intended to ask for algorithms that were both sublinear space and polynomial time. – David Eppstein Aug 17 '14 at 23:03
• @DavidEppstein Yes, exactly. I have edited again for clarification. – felix Aug 18 '14 at 6:51
• BTW, assuming the standard pricing model of 1 per midmatch/delete/insert, then if the edit distance is l, then the path realizing the shortest path in the edit distance matric is going in distance at most l from the main diagonal, and then the edit distance be computed using O(l) space. Thus, with sqrt(n) space, you can compute the edit distance if it is small (i.e., smaller than sqrt(n)). It is only if it is large that this seems hard. Of course, in this case, arguably, you should care less. – Sariel Har-Peled Aug 19 '14 at 21:40

Just to get things going, rather than trying to close out this problem: there is an obvious nondeterministic algorithm using logarithmically many bits of space (search for a single path through the dynamic programming matrix) so by Savitch's theorem there is a deterministic algorithm with space $O(\log^2 n)$. Its time must be of the form $n^{O(\log n)}$, quasi-polynomial rather than exponential.