18
$\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.

Improve this question
$\endgroup$
6
  • 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
    Commented Aug 17, 2014 at 22:42
  • 1
    $\begingroup$ ... Actually, the original Wagner–Fischer algorithm already does that. $\endgroup$
    – Emil Jeřábek
    Commented Aug 17, 2014 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
    Commented Aug 17, 2014 at 23:03
  • $\begingroup$ @DavidEppstein Yes, exactly. I have edited again for clarification. $\endgroup$
    – Simd
    Commented Aug 18, 2014 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
    Commented Aug 19, 2014 at 21:40

1 Answer 1

Reset to default
17
+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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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