12.1. Understanding Intractability

Most of this course has been about identifying efficient solutions to problems. But it is also important to realize that there are some situations where no known efficient solutions exist. This helps us recognize not to fruitlessly search for solutions when problems are known to be hard to solve.

In this chunk, we explore the idea of intractability in computer science. While we've focused on finding efficient solutions, not all problems have such solutions. Understanding that certain problems are intractable prevents us from wasting time trying to find methods that do not exist. This recognition is crucial in both theoretical and practical contexts to save effort and resources.

Imagine a chef trying to cook a recipe that requires a rare ingredient that is unavailable. Instead of searching endlessly for this ingredient, the chef realizes it’s better to choose a different recipe. Similarly, in computer science, when we acknowledge that a problem cannot be solved efficiently, we can move on to problems where solutions are feasible.

Many of the problems that we have seen require searching through a number of possibilities to find some kind of optimum combination. The actual search space can be exponential. For instance, if we're searching for the shortest paths or minimum spanning trees, the number of paths is exponential.

Here, we discuss how problems often involve exploring a vast number of possibilities, which makes searching for solutions complex. The concept of 'exponential search space' means that the number of potential solutions grows rapidly, making it impractical to evaluate every possibility. This is particularly true for problems like shortest paths or minimum spanning trees, where the combinations can become unmanageable very quickly.

Consider a puzzle where you must find the shortest route between multiple cities. Each route represents a possibility, and as more cities are added, the number of routes increases dramatically like a tree branching out. Trying to evaluate all possible routes can be overwhelming without a smarter strategy.

Let’s differentiate between generating a solution and checking a solution. For example, a mathematics teacher assigns the task of finding prime factors of a large number. The student generates a solution by finding the primes, while the teacher checks the solution by multiplying these inputs and verifying whether they equal the original number.

In this part, we clarify the difference between generating a solution and checking a solution. Generating involves actively creating a potential answer, like a student finding factors. Checking, on the other hand, requires validating that a given answer is correct without needing to find it. This distinction is crucial in computational theory as it highlights the efficiency of verification processes compared to solution generation.

Think of baking a cake. The recipe is the solution-generating process. You gather ingredients, mix them, and bake. But once the cake is done, you check if it’s baked properly by using a toothpick to see if it comes out clean. Here, making the cake is generation, while testing its readiness is checking.

A checking algorithm can quickly verify a solution’s validity for a given problem instance by taking inputs and said solution, and deciding whether it meets the criteria.

This chunk focuses on recognizing what a checking algorithm is and its functionality. With a checking algorithm, given a problem and a proposed solution, one can assess whether the solution is accurate or not. This process is generally faster and simpler than generating an answer from scratch, highlighting its significance in algorithmic efficiency.

Returning to the cake example, after baking, you check if it’s done correctly. If the toothpick comes out clean, that validates (or checks) that the cake is baked properly. You don’t have to re-bake the cake; just confirming its readiness suffices, similar to how checking algorithms confirm proposed solutions.

--