# 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