Communications of the ACM
For 40 Years, Computer Scientists Looked For a Solution That Doesn't Exist
Creating a faster method for performing the "edit distance" calculation — a challenge computer scientists have worked on for four decades — was demonstrated as futile by Massachusetts Institute of Technology (MIT) researchers at the recent Symposium on the Theory of Computing conference. The time-consuming operation involves determining the steps needed to convert one sequence of numbers into another, and researchers use the edit distance calculation for such tasks as genomic comparison.
The current edit distance measurement technique is the Wagner-Fischer algorithm, which plots data on a grid and functions in quadratic time. One data string is arranged along the top row of the grid while the other runs down the left-hand column, with the algorithm filling in the grid diagonally and counting changes as it goes. Quadratic time means an increase in the length of the data strings is accompanied by an exponential increase in the number of steps required to compare them.
MIT professor Piotr Indyk and graduate student Arturs Backurs have shown the impossibility of creating a faster edit distance measurement methodology, as dictated by mathematical laws. They demonstrated that a quicker edit distance calculation mechanism would rely on the presence of a stronger variant of the P=NP problem, which most scientists agree is nonexistent.
From The Boston Globe
View Full Article
Abstracts Copyright © 2015 Information Inc., Bethesda, Maryland, USA
No entries found