Sign In

Communications of the ACM

ACM TechNews

For 40 Years, Computer Scientists Looked For a Solution That Doesn't Exist

solution that doesn't exist, illustration

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

Sign In for Full Access
» Forgot Password? » Create an ACM Web Account