Lesson 3

So, we would be very interested in constructing a faster-than-quadratic algorithm for the local alignment problem. We do not know whether such an algorithm exists: on the one hand, no one has come up with such an algorithm so far; on the other hand — we don’t even know how to prove that there is no algorithm solving this problem in linear time!

It turns out that if a faster algorithm exists for the local alignment problem, then the satisfiability problem can also be solved faster than exhaustive search!

Theorem (Abboud, Vassilevska-Williams, 2014). If for the local sequence alignment problem of sequences of length \(n\) there is an algorithm with running time \(O(n^{2-\varepsilon})\), where \(\epsilon > 0\), then for the satisfiability problem there is also an algorithm with running time \(O^{*}((2-\delta(\varepsilon))^{n})\), where \(\delta(\varepsilon)>0\).

The proof of this theorem is cumbersome. To show how such results are actually proved, in the next step we will give a simpler example.