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.
Edit distance in sublinear space
ds.algorithms;edit distance;space time tradeoff