3 ms·
No. Quadratic speed is way too fast for crypto - besides, asymmetric cryptography relies on problems that are difficult to solve but candidate solutions are eas
by Sharlin 11y ago
No. Quadratic speed is way too fast for crypto - besides, asymmetric cryptography relies on problems that are difficult to solve but candidate solutions are easy to validate! This is what the complexity class NP is about. As far as I know there's no way to check a solution for edit distance any faster than it takes to compute it in the first place. Also, the new proof just shows that edit distance is quadratic if P!=NP.
- erikb 11y agoYeah, don't know enough about it.
- Scea91 11y agoI 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.