Stories
Slash Boxes
Comments

SoylentNews is people

SoylentNews is powered by your submissions, so send in your scoop. Only 16 submissions in the queue.
posted by martyb on Sunday August 07 2016, @11:19PM   Printer-friendly
from the close-enough dept.

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

 
This discussion has been archived. No new comments can be posted.
Display Options Threshold/Breakthrough Mark All as Read Mark All as Unread
The Fine Print: The following comments are owned by whoever posted them. We are not responsible for them in any way.
  • (Score: 2) by AnonymousCowardNoMore on Monday August 08 2016, @02:52PM

    by AnonymousCowardNoMore (5416) on Monday August 08 2016, @02:52PM (#385306)

    "This sounds like an NP thing" means that "this"—referring to the research result—is dependant upon the properties of the NP complexity class. Depending on context such a statement could imply that the problem of edit distance is itself either NP-easy or NP-hard but need not; in this instance it does not. Unfortunately there is no such thing as totally unambiguous language. As the summary states, the researchers found that solving the problem in less than quadratic time allows one to solve all problems in NP (i.e. "NP-easy" problems) in less than exponential time. This may be possible even if P == NP (a function may grow faster than polynomials and slower than exponentials) but is considered unlikely (Strong Exponential Time Hypothesis).

    P.S. since you asked for pedantry and made an error (no hate and do feel free to return the favour). A problem which is in NP but has no known P solution is not necessarily any one of these: P-hard, NP-hard, NP-complete, NP-equivalent, NP-intermediate. All you can say is that it is NP-easy and may or may not still be proven to be any of the previous. A problem is NP-complete if it is both itself in NP (NP-easy) and also at least as hard as any other problem in NP (NP-hard), making it exactly as hard as the hardest problems in NP. NP-intermediate is not proven to exist, but if P != NP then a problem in NP could be P-hard without being P-easy or NP-hard. By Ladner's theorem there must be NP-intermediate problems if P != NP.

    Starting Score:    1  point
    Karma-Bonus Modifier   +1  

    Total Score:   2