5 ms·
I suspect most people, even most computer scientists, have a very limited view of complexity theory. When Big-O notation is introduced, and we discuss algorithm
by jcranmer 8y ago
I suspect most people, even most computer scientists, have a very limited view of complexity theory. When Big-O notation is introduced, and we discuss algorithms, we tend to only ever come across them in contexts where the algorithm is "small" polynomial or "small" hidden constants are present. How many people can even name a polynomial algorithm that's worse than cubic, or a polynomial algorithm with a massive hidden constant? In practice, these algorithms tend to be hidden in nasty combinatorial problems which sometimes are themselves contrived mainly to force a solution that slow.
Yet the evidence suggests that, should P=NP, then the polynomial algorithm is going to be of that nasty combinatorial variety. The main reason for this, informally of course, is that NP-complete problems tend to have their NP-completeness arise from specifically hard instances, rather than generally being hard. SAT is NP-complete, but we can solve many SAT queries we care about (undoing cryptographic algorithms are of course the exception--by design). Graph coloring is NP-complete, except if your graph falls into one of several dozen special cases of graphs which covers most we know about. In other words, there's a kernel of instances where there structure is exponentially complex and there's no way to develop heuristics that are meaningfully simpler than "try every possibility until one works." It is possible that there exists some basis that can describe the complex structure in polynomial terms, but this basis would itself have to embed the complexity we see, and as such, it would be one of those combinatorial monstrosities. Think something of the terms of 3^2^16 as your hidden constant (that's the bounds for the "simple" algorithm in the L=SL paper).
- ahelwer 8y agoSomething 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 agoWe 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.
- marcosdumay 8y agoWe 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