-
Recent Posts
- Maximum Likelihood Ranking October 27, 2023
- Randomization Test For Matched Pairs October 13, 2023
- Clustering September 29, 2023
- Shapley-Shubik Voting Power September 15, 2023
- Decoding of Linear Codes September 1, 2023
Recent Comments
Archives
- October 2023
- September 2023
- August 2023
- March 2023
- January 2023
- December 2022
- November 2022
- October 2022
- September 2022
- August 2022
- June 2022
- May 2022
- December 2021
- November 2021
- October 2021
- September 2021
- August 2021
- July 2021
- May 2021
- April 2021
- March 2021
- February 2021
- January 2021
- December 2020
- November 2020
- October 2020
- September 2020
- August 2020
- March 2020
- February 2020
- January 2020
- December 2019
- November 2019
- October 2019
- September 2019
- August 2019
- July 2019
- June 2019
- May 2019
- April 2019
- 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
- Appendix-Graph Theory
- Appendix-Logic
- Appendix: Miscellaneous
- Appendix: Sequencing and Scheduling
- Appendix: Storage and Retrieval
- Chapter 3 Exercises
- Core Problems
- Overview
- Problems not in appendix
- Uncategorized
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 3-sat, Capacitated Spanning Tree, Difficulty 7, ND5, sat
Protected: Multiple Choice Matching
Enter your password to view comments.
Posted in Appendix-Graph Theory
Tagged 3-sat, Difficulty 6, GT55, Multiple Choice Matching, Path With Forbidden Pairs, sat
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