Chapter 11
Revision as of 21:32, 10 September 2020 by Algowikiadmin (talk | contribs) (→Transformations and Satisfiability)
Contents
NP-Completeness
Transformations and Satisfiability
- 11.1. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula:
- 11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
- 11.3. Prove that 4-SAT is NP-hard.
- 11.4. Stingy SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer , find a satisfying assignment in which at most variables are true, if such an assignment exists. Prove that stingy SAT is NP-hard.
- 11.5. The Double SAT problem asks whether a given satisfiability problem has at least two different satisfying assignments. For example, the problem is satisfiable, but has only one solution . In contrast, has exactly two solutions. Show that Double-SAT is NP-hard.
- 11.6. Suppose we are given a subroutine that can solve the traveling salesman decision problem on page 357 in (say) linear time. Give an efficient algorithm to find the actual TSP tour by making a polynomial number of calls to this subroutine.
- 11.7. Implement a SAT to 3-SAT reduction that translates satisfiability instances into equivalent 3-SAT instances.
- 11.8. Design and implement a backtracking algorithm to test whether a set of clause sets is satisfiable. What criteria can you use to prune this search?
- 11.9. Implement the vertex cover to satisfiability reduction, and run the resulting clauses through a satisfiability solver code. Does this seem like a practical way to compute things?
Basic Reductions
- 11.10
- 11.12
- 11.14
- 11.16
- 11.18
- 11.20
Creatvie Reductions
- 11.22
- 11.24
- 11.26
- 11.28
- 11.30
Algorithms for Special Cases
- 11.32
- 11.34
Back to Chapter List