Can the edit distance between two strings of length n be computed in strongly sub-quadratic time? (This is only possible if the strong…
Can the edit distance between two strings of length n be computed in strongly sub-quadratic time? (This is only possible if the strong exponential time hypothesis is false.)
Open the “Other algorithmic problems” section on Wikipedia →
Source: List of unsolved problems in computer science (CC BY-SA 4.0)