| ▲ | nullc 8 hours ago | |
> the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen A common complexity theory misunderstanding is that statements like this applies to all or even most instances-- and it leads to objectively bad engineering of the form "oh look this is actually 3sat, it's unsolvable". (Great fodder for a midwit meme: idiot and genius say "my heuristics go brrr!"-- midwit says "No no no! NP problems can't be efficiently solved!") Any specific instance may be efficiently solvable (and perhaps all instances coming from your particular problem set -- a subset of all possible 3sats). So I would add to that paragraph "at least for some 3sat instances". | ||
| ▲ | marshray 7 hours ago | parent [-] | |
My 2nd grader once brought home a homework sheet with some simple problems involving combinations of coins and I was like "this is unsolvable!" | ||