Protected: Constrained Triangulation
Enter your password to view comments.
Tag Archives: sat
Protected: Undirected Flow With Lower Bounds
Enter your password to view comments.
Protected: Capacitated Spanning Tree
Enter your password to view comments.
Protected: Multiple Choice Matching
Enter your password to view comments.
3-Satisfiability
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.
Satisfiability
On page 46-47, Garey&Johnson list out 6 “basic core” NP-Complete problems. I’ll go over all of them quickly, because they will be used in the reductions for many other problems. But they all start with the “first” NP-Complete problem, Satisfiabiity:
The Problem: Satisfiability (SAT)
The Description: (G&J, p. 39) Given a set U of variables, and a set C of Clauses over U, is there a way to set the variables in U such that every clause in C is true?
(Note that this is not general satisfiability, where the input is any boolean formula. This is really “CNF-Satisfiability”, where the formula is in conjunctive normal form. But you can use logical rules to turn any general logical formula into a CNF formula)
The proof: (p. 39-44) G&J provide a proof of Cook’s Theorem, which provides a “first” NP-Complete problem by representing the formula in non-deterministic Turing Machines. It’s a crazy hard proof, we spent a week (at least) of my graduate school Theory of Computation class going over it, and I still have trouble following it. I think it’s way too hard for undergraduates to follow.
Difficulty: 10