Monthly Archives: June 2014

3-Dimensional Matching

Leave a reply

Last one for today.  I’m not sure how exactly I’ll space these out. We’ll see.

The Problem: 3-Dimensional Matching (3DM)

The Definition: Given disjoint sets W,X,Y all with the same number (q) of elements, and a set M of triples from WxXxY.  Is there a subset M’ of M of size q where no two elements of M’ agree in any coordinate?

I always have trouble picturing what this means, so here’s an example:

Let W = {1,2,3,4}, X = {10,20,30,40}, Y = {100,200,300,400}. q is 4 in this case.

M is a set of triples like (1,30,400), (2,20,100), and so on, with one element from each of W,X, and Y.

We’re asking for q elements of M that have no duplicates in any coordinate.  In other words, each of {1,2,3,4} appears in exactly one element of M’, each of {10,20,30,40} appears in exactly one element of M’, and so on.  So, a legal M’ could be:

{(1,20,300), (2,30,400), (3,40,100), (4,10,200)}

..assuming all 4 of those triples happened to be in the M we were given.

The Reduction: From 3SAT.  Pages 50-52 explain how we take the clauses and build W, X, Y, and M from them.  It’s pretty crazy-M contains 3 kinds of triples for 3 different kinds of jobs, build according to 3 different sets of rules.

Difficulty: 8.  I couldn’t imagine a student coming up with this without a lot of hand-holding.

3-Satisfiability

2 Replies

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

2 Replies

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

Annotated NP-Complete Problems: The overview

Leave a reply

In 1979, Garey&Johnson published  the classic work: Computers and Intractability: A Guide to the Theory of NP-Completeness.  It’s a fantastic book, that every Computer Scientist should own.  The first half of the book describes the theory of NP-Completeness, and shows methods to prove problems NP-Complete.  The last 100 pages list out NP-Complete problems, with a short description of why it’s NP-Complete, along with some other facts.

I teach Computer Science at Ohio Wesleyan University, and one of the courses I regularly teach is our upper-level Analysis of Algorithms class.  One of the subjects in this class is NP-Completeness, and I have students do some reductions on homeworks and tests.  I use the Garey&Johnson book to help me find problems, but when I do, I run across several issues:

1) The book was published in 1979, and many more problems have been discovered since then.

2) For most problems, the authors do not provide a proof of NP-Completeness, just a description of the problem they are reducing from, with a reference to the paper the reduction was made in.  Sometimes, even the reference is missing.

Fixing issue #1 is beyond my ability, though I would dearly love an updated version of this book.  (Though in truth, a modern list of NP-Complete problems would probably be larger than any physical book could contain).  As a teacher, though, issue #2 was an even greater challenge.  When I’m looking for a problem to assign on a homework or test, I’m usually time-constrained (I teach this topic at the end of the semester, when lots of demands are on my time), and I need to determine relatively quickly how hard the reduction will be for the students.  This has proven difficult for me, and I wondered if maybe it was difficult for other faculty as well.

Thus,  I have decided to spend some time building this resource.  The goal is for this to be an ongoing project, where I (eventually, probably over the course of years) go through this book, problem by problem, and for each proof that is not done in the book, provide:

  • A description of the problem
  • A quick sketch of how the reduction will go (this is basically the first step of the proof- where we convert an instance of a known NP-Complete problem to an instance of our problem.)  I find this to be the most difficult, “flash of insight” driven part of the proof.  Hopefully by providing this part, the rest of the proof will fall into place.
  • A ranking of difficulty from 1 (trivial) to 10 (basically impossible to be done by a student just learning this for the first time).  In my classes, I tend to find problems in the 3-6 range to be good choices

Hopefully, this will become a resource for faculty.  I plan on password-protecting older entries so that students can’t find solutions by searching the web.

I fully expect to make mistakes, to have ratings the people disagree with, for other people to find more elegant and simpler reductions, and so on.  Please let me know if any of that happens!

This is not meant to be a place to teach basic NP-Completeness (what a reduction is, why we care about it, anything like that).  That stuff is important, but Garey&Johnson teach it well 🙂

I’ll start with a quick overview of the problems proved in the early part of the book, because they form the “core” from which most of the reductions are based.