4 ms·

Something I've always wondered - if only certain instances of 3SAT are difficult, why are those considered the same problem as easy instances of 3SAT? Why do we

Something I've always wondered - if only certain instances of 3SAT are difficult, why are those considered the same problem as easy instances of 3SAT? Why do we say 3SAT is hard, rather than 3SAT with specific structure? Or do we lack the ability to determine whether a given instance of 3SAT is hard?

jcranmer 8y ago
We use the worst-case analysis to drive Big-O notation; if the worst case is hard, then we say the problem itself is hard. This is the main limitation of Big-O, as normally taught: it tends to ignore the practicability of the algorithm for typical cases. Usually, the practice for solving these sorts of problems is to have your algorithm return three values: the solution, unsatisfiable, or timed out. There is literature on how to structure such problems to make it more likely you're going to get answers, but I'm not personally familiar with this area.
- kosievdmerwe 8y ago
  Yup, I still think that you can likely solve the halting problem for "useful" cases. The cases where you can't you probably should change your code anyways, since odds are people can't reason about it either.
  - DasIch 8y ago
    Almost any application with an event loop doesn’t halt.
    - uryga 8y ago
      you're right, but i'm pretty sure that those programs are not what GP was talking about. i mean, i don't think anyone would be applying a termination checker to a daemon-ish program that's meant to run forever... you'd just check the parts that are actually meant to terminate.
    - kybernetikos 8y ago
      And for many of them, you could determine that statically.
marcosdumay 8y ago
We know that 3SAT is NP-complete. That is, you can use a solution of 3SAT to solve any NP problem with only a polynomial slowdown. There is no such proof for the subset of 3SAT that we can solve quickly. It's for the entire problem only.
pron 8y ago
> Or do we lack the ability to determine whether a given instance of 3SAT is hard? Yes. At least in general. In fact, answering whether any SAT (or 3SAT) instances are hard equivalent to settling P vs. NP. Assuming easy = polynomial, the "easy subset" of SAT = SAT iff P = NP. Separating hard from easy instances -- in general -- is pretty much the secret to complexity theory. We do know to recognize some easy cases. SAT is FPT -- i.e. fixed parameter tractable [1] -- because its worst-case solving time is exponential in the number of variables. There are more complex cases of easy instances. A question that is easier than P vs. NP is separating SAT instances that are easy/hard for DPLL (+ improvements), the 1960s algorithm at the core of all SAT solvers. AFAIK, this, too, is an unanswered question in general (i.e., given a SAT instance, we don't know how to tractably determine whether or not DPLL will tractably solve it). [1]: https://en.wikipedia.org/wiki/Parameterized_complexity#FPT https://en.wikipedia.org/wiki/Parameterized_complexity#FPT

jcranmer 8y ago

We use the worst-case analysis to drive Big-O notation; if the worst case is hard, then we say the problem itself is hard. This is the main limitation of Big-O, as normally taught: it tends to ignore the practicability of the algorithm for typical cases. Usually, the practice for solving these sorts of problems is to have your algorithm return three values: the solution, unsatisfiable, or timed out. There is literature on how to structure such problems to make it more likely you're going to get answers, but I'm not personally familiar with this area.

kosievdmerwe 8y ago
Yup, I still think that you can likely solve the halting problem for "useful" cases. The cases where you can't you probably should change your code anyways, since odds are people can't reason about it either.
- DasIch 8y ago
  Almost any application with an event loop doesn’t halt.
  - uryga 8y ago
    you're right, but i'm pretty sure that those programs are not what GP was talking about. i mean, i don't think anyone would be applying a termination checker to a daemon-ish program that's meant to run forever... you'd just check the parts that are actually meant to terminate.
  - kybernetikos 8y ago
    And for many of them, you could determine that statically.

marcosdumay 8y ago

We know that 3SAT is NP-complete. That is, you can use a solution of 3SAT to solve any NP problem with only a polynomial slowdown. There is no such proof for the subset of 3SAT that we can solve quickly. It's for the entire problem only.

pron 8y ago

> Or do we lack the ability to determine whether a given instance of 3SAT is hard? Yes. At least in general. In fact, answering whether any SAT (or 3SAT) instances are hard equivalent to settling P vs. NP. Assuming easy = polynomial, the "easy subset" of SAT = SAT iff P = NP. Separating hard from easy instances -- in general -- is pretty much the secret to complexity theory. We do know to recognize some easy cases. SAT is FPT -- i.e. fixed parameter tractable [1] -- because its worst-case solving time is exponential in the number of variables. There are more complex cases of easy instances. A question that is easier than P vs. NP is separating SAT instances that are easy/hard for DPLL (+ improvements), the 1960s algorithm at the core of all SAT solvers. AFAIK, this, too, is an unanswered question in general (i.e., given a SAT instance, we don't know how to tractably determine whether or not DPLL will tractably solve it). [1]: https://en.wikipedia.org/wiki/Parameterized_complexity#FPT https://en.wikipedia.org/wiki/Parameterized_complexity#FPT