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