upvote
2n should read as 2^n
reply
Unless OP already solved p=np...
reply
that threw me, thanks
reply
deleted
reply
> 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".

reply
My 2nd grader once brought home a homework sheet with some simple problems involving combinations of coins and I was like "this is unsolvable!"
reply
deleted
reply