It's θ(n²) time with Needleman-Wunsch / Wagner-Fischer. The paper now says that the problem requires Ω(n²) time as long as P ≠ NP. Nothing NP-hard about sequenc

It's θ(n²) time with Needleman-Wunsch / Wagner-Fischer. The paper now says that the problem requires Ω(n²) time as long as P ≠ NP. Nothing NP-hard about sequence alignment, and it also isn't an optimization problem. You are also mixing up two kinds of heuristics. SAT solvers use heuristics to guide the search, making it faster in the expected case (but possibly also slower), but they do not sacrifice correctness. Sequence alignment heuristics sacrifice correctness for speedups. Those are two very different concepts.