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?
$\begingroup$
$\endgroup$
3
-
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 FilmusCommented Nov 8, 2013 at 0:54
-
1$\begingroup$ Have you tried reading the Wikipedia articles about SAT and P vs. NP? $\endgroup$– KavehCommented Nov 8, 2013 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$– RaphaelCommented Nov 8, 2013 at 13:17
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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.
answered Nov 8, 2013 at 0:33
-
$\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$– juaninfCommented Nov 8, 2013 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$ Commented Nov 8, 2013 at 4:10