Runtime Behavior
As mentioned briefly above, though the problem is NP-complete, many practical instances can be solved much more quickly. Many practical problems are actually "easy", so the SAT solver can easily find a solution, or prove that none exists, relatively quickly, even though the instance has thousands of variables and tens of thousands of constraints. Other much smaller problems exhibit run-times that are exponential in the problem size, and rapidly become impractical. Unfortunately, there is no reliable way to tell the difficulty of the problem without trying it. Therefore, almost all SAT solvers include time-outs, so they will terminate even if they cannot find a solution. Finally, different SAT solvers will find different instances easy or hard, and some excel at proving unsatisfiability, and others at finding solutions. All of these behaviors can be seen in the SAT solving contests.
Read more about this topic: Boolean Satisfiability Problem
Famous quotes containing the word behavior:
“Children, randomly at first, hit upon something sooner or later that is their mother’s and/or father’s Achilles’ heel, a kind of behavior that especially upsets, offends, irritates or embarrasses them. One parent dislikes name-calling, another teasing...another bathroom jokes. For the parents, this behavior my have ties back to their childhood, many have been something not allowed, forbidden, and when it appears in the child, it causes high-voltage reaction in the parent.”
—Ellen Galinsky (20th century)