2 ms·
> Do you not realize that SAT might just be O(2^n) at best? Yes, but that's the worst case on all possible instances. Even with this worst case performance, th
by js8 3y ago
> Do you not realize that SAT might just be O(2^n) at best?
Yes, but that's the worst case on all possible instances. Even with this worst case performance, there might be an algorithm that works on par with other algorithms that specialize only on certain instances. E.g. there can be an O(2^n) algorithm for general SAT which performs in O(n^(3/2)) on XORSAT. We simply don't understand the problem well enough to tell.
Also the set of worst-case instances can be vanishingly small in practice.
- constantcrying 3y agoThe average case is also O(n^2). You have a completely utopian idea about what might be computationally feasible. I don't even know what you are arguing. Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction.
- samatman 3y ago> Certainly it is thinkable that SAT is somehow ridiculously simple to calculate, just in the same way that achieving simple and near free fusion energy is thinkable. It just isn't going to happen and speculating on it is pure science fiction. These are, as I'm sure you know, utterly different. Nuclear fusion is real, 'simple' and 'near free' are engineering problems. If human civilization lasts long enough, and continues to progress technologically, we'll have that, for some value of 'simple' and 'near free'. On the other hand, the conjecture that SAT is algorithmically feasible may be disproven, and in my opinion, will be. That would be "just isn't going to happen".