
Recent Posts
 Generalized Geography March 15, 2019
 Sequential Truth Assignment March 8, 2019
 Generalized Hex March 1, 2019
 Quantified Boolean Formulas February 22, 2019
 Integer Expression Membership February 15, 2019
Recent Comments
 Gabriel Ferrer on Quantified Boolean Formulas
 Sean T. McCulloch on Quantified Boolean Formulas
 Gabriel Ferrer on Quantified Boolean Formulas
 Sean T. McCulloch on Quantified Boolean Formulas
 Gabriel Ferrer on Quantified Boolean Formulas
Archives
 March 2019
 February 2019
 January 2019
 December 2018
 November 2018
 October 2018
 September 2018
 August 2018
 July 2018
 June 2018
 May 2018
 April 2018
 March 2018
 February 2018
 January 2018
 December 2017
 November 2017
 October 2017
 September 2017
 August 2017
 July 2017
 June 2017
 May 2017
 April 2017
 March 2017
 February 2017
 January 2017
 December 2016
 November 2016
 October 2016
 September 2016
 August 2016
 July 2016
 June 2016
 May 2016
 April 2016
 March 2016
 February 2016
 January 2016
 December 2015
 November 2015
 October 2015
 September 2015
 August 2015
 July 2015
 June 2015
 May 2015
 April 2015
 March 2015
 February 2015
 January 2015
 December 2014
 November 2014
 October 2014
 September 2014
 August 2014
 July 2014
 June 2014
Categories
 Algebra and Number Theory
 Appendix Algebra and Number Theory
 Appendix Automata and Language Theory
 Appendix Games and Puzzles
 Appendix Mathematical Programming
 Appendix Network Design
 Appendix Program Optimization
 Appendix Sets and Partitions
 AppendixGraph Theory
 AppendixLogic
 Appendix: Sequencing and Scheduling
 Appendix: Storage and Retrieval
 Chapter 3 Exercises
 Core Problems
 Overview
 Problems not in appendix
 Uncategorized
Meta
Tag Archives: sat
Protected: Constrained Triangulation
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Constrained Triangulation, Difficulty 10, ND45, sat
Protected: Undirected Flow With Lower Bounds
Enter your password to view comments.
Posted in Appendix Network Design
Tagged Difficulty 6, Difficulty 8, Mixed graph flow with lower bounds, ND37, sat, Undirected Flow With Lower Bounds
Protected: Capacitated Spanning Tree
Enter your password to view comments.
Posted in Appendix Network Design
Tagged 3sat, Capacitated Spanning Tree, Difficulty 7, ND5, sat
Protected: Multiple Choice Matching
Enter your password to view comments.
Posted in AppendixGraph Theory
Tagged 3sat, Difficulty 6, GT55, Multiple Choice Matching, Path With Forbidden Pairs, sat
3Satisfiability
The first of the “core six” problems, and the first NPComplete problem that’s actually a reduction from a known NPComplete problem.
The Problem: 3Satisfiability (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 “CNFSAT”, most people would call this problem “3CNFSAT”)
The Reduction: From SAT. Pages 4849 give a simple algorithm to convert arbitrarilysized 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 3CNFSAT is NPComplete, the similar problem of 2CNFSAT (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 3CNF to 2CNF, or Fractional Knapsack to 0/1 Knapsackwhere the solution space shrinks!) can drastically affect the complexity of the problem.
Satisfiability
On page 4647, Garey&Johnson list out 6 “basic core” NPComplete 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” NPComplete 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 “CNFSatisfiability”, 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. 3944) G&J provide a proof of Cook’s Theorem, which provides a “first” NPComplete problem by representing the formula in nondeterministic 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 to hard for undergraduates to follow.
Difficulty: 10