Hacker News Reader

Comment by Sharlin | Hacker News Reader

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.

View on HN

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.

The article says it's quadratic, which would put it in P as it's polynomial time.

P is in NP.

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.

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

Yeah, don't know enough about it.

Reply on news.ycombinator.com