12.7. Reduction Between Problems

Try these first

1. 1.

   What is the difference between generating and checking algorithms?

   Hint

   Think about what you do when you receive an answer to a problem.

2. 2.

   Can you give an example of a problem that can be checked but not easily generated?

   Hint

   Recall the definition of SAT and its verification process.

3. 3.

   What distinguishes a generating algorithm from a checking algorithm?

   • A generating algorithm verifies correctness
   • while a checking algorithm generates solutions.
   • A generating algorithm finds solutions
   • while a checking algorithm verifies correctness.
   • Both generate and check solutions simultaneously.

   Hint

   Recall the definitions discussed in class.

4. 4.

   True or False: The Boolean Satisfiability problem can be generated efficiently.

   • True
   • False

   Hint

   Think of the complexity of SAT when generating solutions.

5. 5.

   Design a checking algorithm for the Traveling Salesman Problem that utilizes binary search in conjunction with a distance bound.

   Hint

   Consider using approximations before refining your search with binary search.

6. 6.

   Using the concept of reduction, show how you can demonstrate that finding a maximum independent set is at least as hard as solving the vertex cover problem.

   Hint

   Explore the relationships between nodes and edges in both problems.