Edit Distance: Impossible to calculate in linear time?

In Computer Science, Edit Distance is a technique to calculate number of characters required to be add or removed from a string to make equivalent to another string. We can also use this to quantify how differ a string from another string. This has many application including in Bioinformatics to match two DNA strings.

Recently, two scientists, Indyk and Backurs, found that it is impossible to calculate Edit Distance in less than quadratic time. They proved that Edit Distance problem can be solvable in polynomial time if and only if P equal to NP problems.

Source: http://goo.gl/ocdSfk
The complete paper is available here: http://arxiv.org/abs/1412.0348


Popular posts from this blog


Khuda Karay K Meri Arz -e- Pak Par Utray

کولہوں کے بیل