3-SAT

3-SAT is SAT with a tidy restriction: every clause has exactly three literals. You still ask whether the formula can be made true, but now each OR-group is limited to three switches, like (x1 OR NOT x2 OR x3). This little uniformity makes 3-SAT the workhorse starting point for almost every NP-hardness proof, because three-literal clauses are just structured enough to build neat gadgets from.

A 3-CNF formula is an AND of clauses, each clause an OR of exactly three literals, each literal a variable or its negation. 3-SAT asks: is there a true/false assignment satisfying every clause? The remarkable fact is that this restricted version is still NP-complete. You reduce general SAT to 3-SAT by chopping up clauses: a clause with one or two literals is padded with helper variables, and a long clause like (a OR b OR c OR d OR e) is split into a chain (a OR b OR y1) AND (NOT y1 OR c OR y2) AND (NOT y2 OR d OR e) using fresh variables y1, y2 that thread the choices together. The new formula is satisfiable exactly when the old one was, and it has only three literals per clause.

Why prefer 3-SAT over plain SAT as a reduction source? Because the rigid 'exactly three literals' shape is far easier to translate into the structures of graph problems. Reductions from 3-SAT to CLIQUE, to vertex cover, to graph colouring, and to Hamiltonian path are the classic gadget constructions of the field. Note the boundary: 3-SAT is NP-complete, but 2-SAT (two literals per clause) is solvable in polynomial time. The jump from two to three literals is exactly where tractability gives way to NP-completeness.