Independent Subproblems

A reduction can change only the size of the problem, but not the problem itself. So, we should look for smaller subproblems that are as independent as possible. There is a way to overcome the limitation that the reduced problem must be identical to the original problem: Change the problem statement. Sometimes, it is better to weaken the hypothesis and to arrive at a weaker algorithm, which can be used as a step in the complete algorithm.

Let’s unpack that paragraph step by step.

1. Independent Subproblems: In many computational problems, a large problem can be broken down into smaller, independent subproblems. Solving each subproblem independently can often lead to the solution for the overall problem. This is a central concept in dynamic programming, where the problem is divided into overlapping subproblems, and the solutions to these subproblems are stored to avoid redundant computation. In divide-and-conquer algorithms, the problem is broken down into independent, non-overlapping subproblems.

2. Reduction and Problem Size: “Reduction” in computer science usually means transforming one problem into another, with the intention that a solution to the second problem can easily be transformed into a solution for the first. A common type of reduction, called a polynomial reduction, ensures that if the second problem can be solved quickly (in polynomial time), then the first problem can too. The goal of reduction is to reduce the size of the problem or convert it to a problem that we know how to solve.

3. Changing the Problem Statement: Sometimes, it might be easier to solve a slightly different problem than the one you were initially given. By altering the problem statement (within reason), you can turn a hard problem into an easier one. Once you’ve solved the easier problem, you can then try to adjust your solution to handle the added complexity of the original problem.

4. Weakening the Hypothesis: This refers to making the conditions of the problem more general. While this might lead to a “weaker” algorithm (one that solves a broader class of problems but might not be as efficient or precise for the specific problem), it can provide a starting point. The solution to the more general problem can sometimes be refined or adapted to better solve the specific problem.

To summarize, when faced with a complex problem, one approach is to break it down into independent subproblems, alter the problem to make it easier, or solve a more general version of the problem. Each of these strategies can provide a way forward when the problem seems intractable.