← Back to context

Comment by ehershey

10 hours ago

I like this https://www.reddit.com/r/explainlikeimfive/comments/33fmrq/e...

  In computer science, the satisfiability problem is the task of determining whether a boolean problem can be satisfied, that is, made to be true, by some combination of inputs. For example, the expression: A AND NOT B is satisfied whenever A is true and B is false, while the expression: A AND NOT A cannot be satisfied.
  A naive approach to satisfiablilty would be to check every possible input and see if the expression evaluates to true. 
  However, the number of combinations that must be checked is 2n, where n is the number of variables in the expression. This is what is meant by exponential time.
  The exponential time hypothesis conjectures that you cannot do better, that is, the number of operations needed to solve satisfiability will always be exponential in the size of the problem, no matter what algorithm is chosen.
  If this hypothesis is true, it would imply that P≠NP, because satisfiability has been shown to be in NP, and in order for it to be in P there would have to exist an algorithm that solves it in polynomial time.

7 comments

ehershey

Reply
nullc  10 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  9 hours ago

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