3 ms·

This is so wrong. Just because it's NP-hard (optimization problem, right?) it doesn't mean that there aren't very-very-very good heuristic algorithms that can m

by zerokk 11y ago

This is so wrong. Just because it's NP-hard (optimization problem, right?) it doesn't mean that there aren't very-very-very good heuristic algorithms that can make the search significantly faster than exponential in the vast majority of the cases. Take a look at SAT solvers and see how deep the rabbit hole really goes.

epistasis 11y ago
Heuristic algorithms can never be "optimal". The article is precise and correct. I use heuristic algorithms for all my DNA alignment, and for all my probabilistic modeling, but I do that with the knowledge that I'm not necessarily finding an optimal solution, I'm only find a "pretty good" solution like the SAT solvers do.
mafribe 11y ago
It's questionable whether SAT solvers really work well for "the vast majority of the cases". They work very well for the problems they are tasked with. DPLL-based SAT solvers don't work well with randomly generated SAT instances which survey-propagation-based solvers excel on. On SAT-instances that arise in the verification of CPUs the opposite is true. Both approaches break down where SAT instances have more than 10^7 variables, and that's almost all cases. ;) Still, it never ceases to amaze me just how well DPLL-based solvers work on the instances that I feed them, and that despite all the theoretical limitations that we know they have.
lorenzhs 11y ago
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.

by zerokk 11y ago

epistasis 11y ago

Heuristic algorithms can never be "optimal". The article is precise and correct. I use heuristic algorithms for all my DNA alignment, and for all my probabilistic modeling, but I do that with the knowledge that I'm not necessarily finding an optimal solution, I'm only find a "pretty good" solution like the SAT solvers do.

mafribe 11y ago

It's questionable whether SAT solvers really work well for "the vast majority of the cases". They work very well for the problems they are tasked with. DPLL-based SAT solvers don't work well with randomly generated SAT instances which survey-propagation-based solvers excel on. On SAT-instances that arise in the verification of CPUs the opposite is true. Both approaches break down where SAT instances have more than 10^7 variables, and that's almost all cases. ;) Still, it never ceases to amaze me just how well DPLL-based solvers work on the instances that I feed them, and that despite all the theoretical limitations that we know they have.

lorenzhs 11y ago

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.