19
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Regarding the edit: I think you misunderstand something. David Eppstein’s answer shows the problem is solvable in NL, hence also in P. $\endgroup$ – Emil Jeřábek Aug 17 '14 at 22:42
  • 1
    $\begingroup$ ... Actually, the original Wagner–Fischer algorithm already does that. $\endgroup$ – Emil Jeřábek Aug 17 '14 at 22:54
  • 3
    $\begingroup$ I assume the edited version intended to ask for algorithms that were both sublinear space and polynomial time. $\endgroup$ – David Eppstein Aug 17 '14 at 23:03
  • $\begingroup$ @DavidEppstein Yes, exactly. I have edited again for clarification. $\endgroup$ – felix Aug 18 '14 at 6:51
  • $\begingroup$ 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. $\endgroup$ – Sariel Har-Peled Aug 19 '14 at 21:40
16
+25
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ How do you verify the path you have found is optimal? $\endgroup$ – Lembik Aug 16 '14 at 18:48
  • 1
    $\begingroup$ 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. $\endgroup$ – David Eppstein Aug 16 '14 at 20:00
  • $\begingroup$ @David I think you are correct so I have deleted my answer. $\endgroup$ – SamiD Aug 24 '14 at 20:48
  • 2
    $\begingroup$ Is it even computable in log space? $\endgroup$ – Lembik Aug 26 '14 at 8:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.