# 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:
$\displaystyle{ (x\or y \or \overline z \or w \or u \or \overline v) \and (\overline x \or \overline y \or z \or \overline w \or u \or v) \and (x \or \overline y \or \overline z \or w \or u \or \overline v)\and (x \or \overline y) }$

11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
$\displaystyle{ (x \or \overline y \or z) \and (\overline x \or y \or \overline z) \and(\overline x \or y \or z) \and (x \or \overline y \or \overline x) }$

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 $\displaystyle{ k }$, find a satisfying assignment in which at most $\displaystyle{ k }$ 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 $\displaystyle{ {{v1, v2}, {v_1, v_2}, {v_1, v_2}} }$ is satisfiable, but has only one solution $\displaystyle{ (v_1 =F, v_2 = T) }$. In contrast, $\displaystyle{ {{v_1, v_2}, {v_1, v_2}} }$ 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?

11.10

11.11

11.12

11.13

11.14

11.15

11.16

11.17

11.18

11.19

11.20

11.21

11.22

11.23

11.24

11.25

11.26

11.27

11.28

11.29

11.30

### Algorithms for Special Cases

11.31

11.32

11.33

11.34

11.35

Back to Chapter List