Tag Archives: Difficulty 10

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