SoylentNews is people
SoylentNews
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.
(Score: 2, Interesting) by khallow on Monday August 08 2016, @12:39AM
A key aspect of the paper is the construction of "gadget sequences" which allow one to reconstruct the two strings of the Wagner-Fischer (W-F) distance comparison, but in turn allow a two-way "reduction" (I gather this means that a problem is shown to be computationally equivalent to a subset of another problem, "two-way" means that a converse relation is shown as well) of the original problem with something called the "Orthogonal Vectors Problem" (showing that given two finite sets of finite dimensional vectors, there exists at least one pair of orthogonal vectors taken one from each set) which apparently has already been shown to be of a similar computational complexity and already shown to have the desired computation relation to "SAT" (determining whether certain boolean expressions can be true), a standard category of NP hard problems.
The paper as well as the Phys.org article note that this gadget sequence approach has already been used in other research papers.
I would like to know more about gadget sequences. It appears necessary to have something like the W-F distance in order to construct the gadgets, but I'm not sure.
(Score: 1) by khallow on Monday August 08 2016, @12:42AM
to "SAT" (determining whether certain boolean expressions can be true), a standard category of NP complete problems