I'm studing P and NP complexity classes. I like know, why is SAT not in P? Is it because I can not determine if any Boolean expression is satisfiable?

  • 3
    $\begingroup$ We don't know whether SAT$\notin$P or not, and we certainly don't have any idea why that would be true (other than geometric complexity theory). $\endgroup$ – Yuval Filmus Nov 8 '13 at 0:54
  • 1
    $\begingroup$ Have you tried reading the Wikipedia articles about SAT and P vs. NP? $\endgroup$ – Kaveh Nov 8 '13 at 2:06
  • $\begingroup$ Please read our reference question on this topic; I'm closing as duplicate since the answer to your (quite uninformed, to be honest) question is there. $\endgroup$ – Raphael Nov 8 '13 at 13:17

It is possible to determine whether a boolean expression is satisfiable, the question is how quickly it can be done.

If there are $n$ variables, then we can try all $2^{n}$ possible truth assignments, and eventually we'll find if there is a satisfying one, but this is not polynomial time with respect to the size of the input.

There might be some polynomial time algorithm that does solve SAT, we don't know, however SAT is NP-complete, which gives strong evidence that there isn't a polynomial time algorithm. It all comes down to whether P=NP or not.

  • $\begingroup$ I'm confusing, The SAT problem is finding a formula such that is satisfiable for all entries? Or is finding a set of assignments to the formula such that it is satisfiable? Or is finding several formulas that are satisfiable for all entries? $\endgroup$ – juaninf Nov 8 '13 at 1:12
  • 1
    $\begingroup$ In the SAT problem, you are given a boolean formula, and you want to know if there's at least one way to satisfy it. So your second definition. $\endgroup$ – Luke Mathieson Nov 8 '13 at 4:10

Not the answer you're looking for? Browse other questions tagged or ask your own question.