<p>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.</p>

<p>There are some space lower bounds for edit distance in <a href="http://arxiv.org/abs/1106.4412">http://arxiv.org/abs/1106.4412</a> but I don't think they match your version of the problem.</p>

CC BY-SA 3.0
2014-08-16T18:48:18.870Z
How do you verify the path you have found is optimal?
Simd
CC BY-SA 3.0
2014-08-16T20:00:47.910Z
Binary search or sequential search for the smallest distance for which a path can be found, i.e., nothing beyond the standard equivalence of decision and search problems. This doesn't affect the forms of either the space or time bound.
David Eppstein
CC BY-SA 3.0
2014-08-24T20:48:41.250Z
@David I think you are correct so I have deleted my answer.
SamiD
CC BY-SA 3.0
2014-08-26T08:52:26.140Z
Is it even computable in log space?
Simd
CC BY-SA 3.0
2014-08-15T19:07:29.667Z
2014-08-15T19:07:29.667Z
David Eppstein
<p>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?</p>

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

<hr>

<p><strong>Edit.</strong> 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.</p>

CC BY-SA 3.0
2014-08-17T22:42:37.380Z
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
CC BY-SA 3.0
2014-08-17T22:54:08.023Z
... Actually, the original Wagner–Fischer algorithm already does that.
Emil Jeřábek
CC BY-SA 3.0
2014-08-17T23:03:23.087Z
I assume the edited version intended to ask for algorithms that were both sublinear space and polynomial time.
David Eppstein
CC BY-SA 3.0
2014-08-18T06:51:45.690Z
@DavidEppstein Yes, exactly.  I have edited again for clarification.
Simd
CC BY-SA 3.0
2014-08-19T21:40:39.667Z
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
CC BY-SA 3.0
2014-08-26T08:55:11.020Z
@SarielHarPeled Can you output the edits needed in O(l) space as well?
Simd
<ds.algorithms><edit-distance><space-time-tradeoff>
Edit distance in sublinear space
Simd
# Edit distance in sublinear space

(Asked by: username_0 on 2014-08-13)

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.

**Tags:** ds.algorithms, edit-distance, space-time-tradeoff
> **Comments:**
> **username_1**: Regarding the edit: I think you misunderstand something. David Eppstein’s answer shows the problem is solvable in NL, hence also in P.  
> **username_1**: ... Actually, the original Wagner–Fischer algorithm already does that.  
> **username_2**: I assume the edited version intended to ask for algorithms that were both sublinear space and polynomial time.  
> **username_0**: @DavidEppstein Yes, exactly.  I have edited again for clarification.  
> **username_3**: 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.  
> **username_0**: @SarielHarPeled Can you output the edits needed in O(l) space as well?  

---

## 1 answers

### Answer by username_2 on 2014-08-15. Score: 17

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.

There are some space lower bounds for edit distance in <http://arxiv.org/abs/1106.4412> but I don't think they match your version of the problem.

> **Comments:**
> **username_0**: How do you verify the path you have found is optimal?  
> **username_2**: Binary search or sequential search for the smallest distance for which a path can be found, i.e., nothing beyond the standard equivalence of decision and search problems. This doesn't affect the forms of either the space or time bound.  
> **username_4**: @David I think you are correct so I have deleted my answer.  
> **username_0**: Is it even computable in log space?  

---

