12.1. Understanding Intractability

Try these first

1. 1.

   What does intractability refer to?

   Hint

   Think about computational complexity.

2. 2.

   Define a checking algorithm.

   Hint

   Consider how you would verify homework answers.

3. 3.

   What is an example of an intractable problem?

   • Sorting a list
   • Traveling Salesman Problem
   • Checking if a number is prime

   Hint

   Think about problems that involve exponential complexity.

4. 4.

   True or False: A checking algorithm can find a solution to a given problem.

   • True
   • False

   Hint

   Remember the roles of checking versus generating.

5. 5.

   Given a graph, devise a method to determine if it contains an independent set of size K.

   Hint

   Remember the definition of independence in sets.

6. 6.

   How would you approach the Traveling Salesman Problem using bounding techniques?

   Hint

   Think about narrowing down the possibilities through incremental checking.