Levenshtein distance
It has been shown that the Levenshtein distance of two strings of length cannot be computed in time for any ε greater than zero unless the strong exponential time hypothesis is false.