# Difference between revisions of "Chapter 11"

Jump to navigation
Jump to search

Line 3: | Line 3: | ||

===Transformations and Satisfiability=== | ===Transformations and Satisfiability=== | ||

− | :[[11.1]] | + | :[[11.1]]. Give the 3-SAT formula that results from applying the reduction of SAT to 3-SAT for the formula: |

+ | :::<math> (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) </math> | ||

+ | [[11.1|Solution]] | ||

− | :11.2 | + | :11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression |

+ | :::<math>(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) </math> | ||

− | :[[11.3]] | + | :[[11.3]]. Prove that 4-SAT is NP-hard. |

+ | [[11.3|Solution]] | ||

− | :11.4 | + | :11.4. ''Stingy'' SAT is the following problem: given a set of clauses (each a disjunction of literals) and an integer <math>k</math>, find a satisfying assignment in which at most <math>k</math> variables are true, if such an assignment exists. Prove that stingy SAT is NP-hard. |

− | :[[11.5]] | + | :[[11.5]]. The ''Double SAT'' problem asks whether a given satisfiability problem has '''at least two different satisfying assignments'''. For example, the problem <math>{{v1, v2}, {v_1, v_2}, {v_1, v_2}}</math> is satisfiable, but has only one solution <math>(v_1 =F, v_2 = T)</math>. In contrast, <math>{{v_1, v_2}, {v_1, v_2}}</math> has exactly two solutions. Show that Double-SAT is NP-hard. |

+ | [[11.5|Solution]] | ||

− | :11.6 | + | :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]] | + | :[[11.7]]. Implement a SAT to 3-SAT reduction that translates satisfiability instances into equivalent 3-SAT instances. |

+ | [[11.7|Solution]] | ||

− | :11.8 | + | :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]] | + | :[[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.9|Solution]] | |

===Basic Reductions=== | ===Basic Reductions=== |

## Revision as of 21:32, 10 September 2020

## 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:
- [math]\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) }[/math]

- 11.2. Draw the graph that results from the reduction of 3-SAT to vertex cover for the expression
- [math]\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) }[/math]

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