The SAT Problem

SAT: Satisfied

<aside> 💡 Given a set of Boolean or Propositional variables each taking a value from {true, false} or {1, 0}, and a formula F involving these variables, to find a valuation for the variables such that the formula F is satisfied (becomes true)

</aside>

Conjuctive Normal Form (CNF)

Each clause has to be satisfied or made true.

For example,

$$ F = (a \lor \neg b \lor e) \land b \land (\neg c \lor d \lor f) \land (d \lor \neg e) \land (\neg a \lor b \lor d) \land (a \lor \neg d) $$

For $N$ variables there are $2^N$ candidates (the state space)

Complexity of SAT

2SAT

• problems where each clause has at most two literals
• known to be in P

3SAT

• problems where each clause has at most three literals
• known to be NP-complete

Probability of 3SAT Variables being satisfied

m: clauses

n: variables