2 ms·
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,
by 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 agoYup, 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 agoAlmost any application with an event loop doesn’t halt.
- uryga 8y agoyou'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 agoAnd for many of them, you could determine that statically.