A New Map Traces the Limits of Computation
Quanta Magazine (09/29/15) John Pavlus
At a recent symposium, Massachusetts Institute of Technology (MIT) researchers presented a mathematical proof that the current best algorithm is optimal, which means it is not mathematically possible to find a more efficient way to compute edit distance; but this is only true if the strong exponential time hypothesis (SETH) proves to be valid. Stanford University professor Ryan Williams thinks SETH is false, and is attempting to refute it. However, Williams contends SETH is useful as a tool to plot out the topography of computational complexity, regardless of whether it is true or not. SETH is a hardness assumption about Boolean satisfiability (SAT), or whether a generic problem is at all solvable. Most computer scientists believe the only general-purpose technique for finding the solution to a SAT problem involves individually trying all possible settings of the variables. SETH’s ramification is that finding a better general-purpose SAT algorithm is an impossibility, and the MIT researchers demonstrated a link between the complexity of edit distance and that of k-SAT, which implied edit distance would take perhaps a millennium to run when applied to actual tasks such as genome comparisons, where variables run into the billions. “If I want to refute SETH, I just have to solve edit distance faster,” Williams says.
Source: ACM TechNews