SoylentNews

fork(2) writes:

If you studied computer science, you most likely encountered the Wagner-Fischer algorithm for edit distance in whatever course introduced 2D arrays. The edit distance between two strings of symbols is the minimum number of edits (insertions, deletions, and substitutions) necessary to turn one string into the other. The algorithm builds a huge table with symbols of one string labeling the rows and symbols from the other labeling the columns. Each entry in the table is the the number of edits required to turn the string ending with the corresponding column into the string ending with the corresponding row.

For years people have been trying to improve on this basic algorithm. And failing. Now, Phys.org is reporting on a paper to appear at ACM Symposium on Theory of Computing (STOC) next week which shows that Wagner-Fischer is as good as it's likely going to get. This sounds like an NP thing..and it is! If it were possible to solve the edit distance problem in less than quadratic time (i.e. faster than filling up the huge table), then it would be possible to solve the satisfiability problem in less than exponential time.

From Phys.org:

Theoretical computer science is particularly concerned with a class of problems known as NP-complete. Most researchers believe that NP-complete problems take exponential time to solve, but no one's been able to prove it. In their STOC paper, [Piotr] Indyk and his student Arturs Backurs demonstrate that if it's possible to solve the edit-distance problem in less-than-quadratic time, then it's possible to solve an NP-complete problem in less-than-exponential time. Most researchers in the computational-complexity community will take that as strong evidence that no subquadratic solution to the edit-distance problem exists.

Original Submission