Sometimes a problem is simply too complex for us to solve. Our only chance seems to be breaking it into smaller parts that we know how to deal with.

This strategy of reducing the complexity of a problem by dividing it into simpler sub-problems is known as “Divide-and-Conquer”. In this case there are two assumptions that are normally true:

• A problem can be divided in several parts, so that each part can be handled independently.
• Handling each one of the smaller parts that compose a problem is less complex than handling the whole problem, and thus we can “conquer” it.

There are several algorithms that are based in this strategy. For example, the Quicksort algorithm works by recursively dividing the list of values to be sorted into two smaller lists, in which one sub-list has the smaller values and the other the bigger values.

Another example is the Motion Planning problem in robotics, in which the robot needs to find a path to cross a room avoiding several obstacles. It is possible to adopt a divide-and-conquer approach to solve this problem, so that each obstacle is treated independently: The robot first finds possible paths between each pair of obstacles, then merges these smaller steps to create a single plan to pass all obstacles.

Given a complex problem, these are the steps that must be followed to solve it using a divide-and-conquer strategy:

1. Define a method to decompose the complex problem into smaller parts.
2. For each part, find a way to solve it.
3. Combine the solutions of the parts to obtain the solution of the original problem.

Some problems can be solved recursively, as in the example of Quicksort. In this case all sub-problems are solved in the same way in step 2, and it is relatively easy to combine their solutions in step 3.

In the case of a problem that cannot be decomposed recursively, each sub-problem in step 2 may require a different solution, and it may be more difficult to combine the solutions in step 3. This would be the case of Motion Planning if the robot needs to do other types of tasks besides only crossing obstacles. For example, in the middle of its path the robot may be required to recharge its batteries or to carry some object.

In any case, a divide-and-conquer strategy will provide a systematic way to cope with complexity, making difficult problems more tractable by our limited human capabilities.