Computational Complexity

Sometimes it is far easier to describe how one would go about solving a problem than to actually solve it. This is particularly true when finding the solution requires a huge number of (albeit simple) steps. For instance, ``Try out all the possibilities and pick the best one,'' is a potential method for solving many problems, but when you begin to consider the number of possibilities that you will have to try, the method is often unrealistic for actually producing a solution.

Determining whether a map will require four colors or just three (see The Most Colorful Math of All) or solving the Ice Cream Stands Problem for a very large map (see Ice Cream and Algorithms for All are examples of such problems.

Because computers are so fast at solving many types of problems, we are tempted to generalize and assume that they can perform any repeated series of steps in a short amount of time. But this is not always the case. For example, it has been suggested that a computer program which checks all the possible outcomes for chess moves would still not be ready to recommend the second move in a game which began when the Big Bang happened.

Computational complexity is the study of such problems, potential methods for their solutions, and the amount of computer resources it would require to solve them.