The Exponential Time Hypothesis and Fine-Grained Complexity
Symptom You have a string algorithm. Edit distance between two sequences, the classic dynamic program, $O(n^2)$ time. It has been in production for years. Now the inputs are genome-scale. At $n = 10^5$ characters, $n^2 = 10^{10}$ operations, about 10 seconds at a billion ops per second. At $n = 10^6$ it is $10^{12}$ operations, about 1000 seconds — seventeen minutes for one pair of strings. You need to do a million pairs. ...