A 3-SAT instance has Boolean variables and clauses. Each clause lists at most three variables or negations, and is satisfied when at least one listed choice is true. A solution must satisfy every clause with one shared assignment.
With n variables there are 2 to the power of n possible assignments. Testing all assignments is a baseline approach, but that count alone does not prove that a faster algorithm is impossible.
ELI5
For example, imagine a row of switches and a list of rules. One rule might say the red switch must be on, or the blue switch must be off, or the green switch must be on.
Your job is to find one setting for all the switches that obeys every rule at the same time.
What does the 3 mean?
It limits the number of choices in each rule. The whole puzzle can contain many more than three switches.
Does a 3-SAT solver need to find every solution?
The decision problem asks only whether any satisfying assignment exists. A single valid assignment is enough to show that the answer is yes.
