| ▲ | ehershey 8 hours ago | |||||||||||||
I like this https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e... | ||||||||||||||
| ▲ | gberger 8 hours ago | parent | next [-] | |||||||||||||
2n should read as 2^n | ||||||||||||||
| ||||||||||||||
| ▲ | 8 hours ago | parent | prev | next [-] | |||||||||||||
| [deleted] | ||||||||||||||
| ▲ | 8 hours ago | parent | prev | next [-] | |||||||||||||
| [deleted] | ||||||||||||||
| ▲ | nullc 8 hours ago | parent | prev [-] | |||||||||||||
> 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". | ||||||||||||||
| ||||||||||||||