12. Intractability: Checking Algorithms

Most of this course has been about identifying efficient solution to problems. But it is also important to realize that there are some situations, where no known efficient solutions exists, and we are able to recognize this, so that we do not fruitlessly try to look for solutions, where the problem is known to be hard to solve.

In this chunk, the focus is placed on the concept of intractability, which refers to problems that cannot be solved efficiently. The course previously discussed how to find efficient solutions, but it is critical to understand that certain problems do not possess efficient solutions. This realization helps prevent wasting time trying to solve problems that are inherently difficult.

Consider a student attempting to solve a complicated math problem. If they know beforehand that there is no simple solution, they can focus their efforts elsewhere instead of struggling fruitlessly with that specific problem.

Many of the problems that we have seen, we are trying to search through a number of possibilities to arrive at some kind of optimum combination. The actual search space is exponential, if we are looking for shortest paths, there are an exponential number of paths.

This chunk describes how many problems involve searching an exponential number of possibilities in order to find optimal solutions. For example, when searching for the shortest path or minimum spanning tree, the number of potential paths or trees is exponentially large. This exponential growth makes it infeasible to try all combinations to find an optimal solution, which is where the intractability of these problems becomes evident.

Imagine you are trying to find your way through a large city. If you were to explore every possible route to reach your destination, the number of routes could be overwhelming and impractical to navigate, similar to how algorithmic problems can grow exponentially as more options are considered.

To get into this discussion, let us talk about the problem between, the difference between generating a solution and checking a solution. Supposing a school Math's teacher assigns a task: take a large number known to be the product of two prime numbers and find these two prime numbers.

In this section, the difference between generating solutions and checking solutions is introduced. When tasked with finding two prime numbers that multiply to a given large number, the student attempts to generate the solution. However, the teacher's job can be simplified to checking the student's solution by multiplying the provided numbers and confirming whether the result matches the original number. This highlights the utility of checking algorithms, which can verify solutions without needing to generate them.

Think of a chef who wants to check if a recipe is correctly followed. Instead of cooking the entire dish themselves to verify its success, they can taste the dish and judge if it matches their expectations. This is similar to how checking algorithms evaluate proposed solutions.

In this context, let us look at a very canonical problem which has a checking algorithm called Boolean satisfiability. The goal is to find out whether this given formula can be made true by assigning suitable values to x, y, and z.

This chunk introduces the Boolean satisfiability problem, where the objective is to determine if there exists an assignment of true or false values to Boolean variables that can satisfy a given formula. By checking whether each clause in the formula holds true under a specific assignment, we can verify the validity of a proposed solution. This problem is fundamental in computer science and illustrates the nature of checking algorithms.

Imagine a group of friends trying to decide on a movie based on different criteria. Each person's preferences can be seen as clauses in a logical formula. The challenge is to find an arrangement of movie selections that meets everyone’s criteria, similar to assigning truth values to the Boolean variables to satisfy the entire formula.

The solution is such optimization problems to convert them into checking algorithms is to transform the problem by giving a bound. We can check if a tour is with cost at most K, thereby simplifying the checking process.

In this section, the strategy for transforming optimization problems into checking algorithms is discussed. By introducing bounds on costs or values, we can ask whether there exists a solution within specific constraints (like costs not exceeding K). This simplification allows for easier checking processes while still seeking to find optimal solutions without generating them explicitly.

Consider a shopping spree with a budget. If you know you have a limit on how much you can spend, you can quickly check if your cart exceeds your budget instead of calculating total prices of every possible combination of items. This is akin to setting bounds on the solution space in algorithmic problems.

--