3 ms·
I get what you mean but 'easy to validate' in the context of NP means 'can be validated in polynomial time'. It seems to me that you imply that edit distance is
by Scea91 11y ago
I get what you mean but 'easy to validate' in the context of NP means 'can be validated in polynomial time'. It seems to me that you imply that edit distance is harder to validate than problems in NP. Edit distance itself is in NP since P is in NP.
- bbrazil 11y agoThe article says it's quadratic, which would put it in P as it's polynomial time.
- Scea91 11y agoP is in NP.
- Sharlin 11y agoI 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.
- wolfgke 11y ago> 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.