> I mean that there needs to be a fundamental difference between the > difficulty of finding a solution and validating one. There's none in > case of edit

> I mean that there needs to be a fundamental difference between the > difficulty of finding a solution and validating one. There's none in > case of edit distance. If you consider the decision problem "Is the edit distance <= d?", there is (according to this result) a fundamental difference - though only a polynomial one. To see this, consider the following argument: Clearly the edit distance between strings of length m, n is bounded by m+n (>= d). So if we found a way to transform the string s1 into s2 using d steps, we can construct a certificate of length O(m+n) (worst case) steps, which can be verified in linear time. On the other hand (according to this result) you need Omega(m*n) (worst case) steps to find such a certificate.