The first of the “core six” problems, and the first NP-Complete problem that’s actually a reduction from a known NP-Complete problem.

**The Problem: **3-Satisfiability (3SAT)

**The Definition:** (p.46) Given a set of variables U, and a set C of clauses, where each clause has exactly 3 elements, can we assign true/false values to the variables in U that satisfies all of the clauses in C?

(Note that just as the Satisfiability problem was really “CNF-SAT”, most people would call this problem “3-CNF-SAT”)

**The Reduction:** From SAT. Pages 48-49 give a simple algorithm to convert arbitrarily-sized clauses into clauses of size 3, possibly by adding some extra variables.

**Difficulty: **6. It’s pretty fiddly to come up with the conversions in all cases. But this really depends on the students’ familiarity with Boolean logic.

As an aside, I find myself compelled to note that while 3-CNF-SAT is NP-Complete, the similar problem of 2-CNF-SAT (where all clauses are of size 2) can be solved in polynomial time. To me, one of the coolest things in Computer Science is how such small changes to a problem (like 3-CNF to 2-CNF, or Fractional Knapsack to 0/1 Knapsack-where the solution space shrinks!) can drastically affect the complexity of the problem.

SurekhaCan you please explain in simple terms how to reduce 3SAT to ONE-IN-THREE-3SAT

Sean T. McCullochPost authorThere are lots of examples out there if you search for it. I found this one pretty quickly: https://www.nitt.edu/home/academics/departments/cse/faculty/kvi/NPC-3SATs.pdf