For computer scientists, the word complexity denotes the amount of work required to solve a problem using a given algorithm.
An algorithm is the sequence of arithmetic and logical operations that lead to the solution of a problem. Computer scientists measure the complexity of an algorithm by comparing the number of instructions that a computer executes in running the algorithm to completion with the size of the input given to the algorithm. If the complexity of a problem is very great, then a practical solution might remain out of reach even to the computer scientist who has an algorithm for the solution of the problem.
Here to illustrate the meaning of computational complexity are two problems:
- Checking to see if a person\’s name and number in a big city’s telephone directory takes longer than finding a name and number in a
small city ‘s directory. How much longer? - An eccentric hiker prefers to carry a knapsack that weighs exactly 42 pounds. At home, the hiker has a closet full of items that might be handy to have in the woods. The hiker has labeled each of those items with its weight. The time required to determine whether or not some combination adds up to the magic number 42 will depend upon the number of articles from which the hiker chooses. How does the time
required to solve this problem relate to the number of items in the
hiker’s closet?
You can find a name in a directory by repeatedly dividing the book in half.
- Hold the book in two hands. Open the directory at the middle with your thumbs.
- Directories list names alphabetically, so you can tell in which half to continue your search. Open to the middle of either the front or back half of the book.
- Divide that quarter into eighths, then the eighth into sixteenths, and so on until you have narrowed the search to a single page.
- If there is a listing, the page on which you land at the last step of your search will contain it.
The number of times we must divide a number by two until we reduce it to one is the logarithm base 2 of that number (rounded up). The function grows slowly. You will have to look at no more than 5 pages to find a name in a directory that contains 32 pages. You will have to look at no more than 6 pages in a 64 page directory, 10 pages in a 1000 page directory, 20 pages in a million page directory, and only 30 pages in a billion page book. Imagine even a billion billion trillion pages—checking 100 pages will get you to the page you want. The complexity of this algorithm (called binary search) is low.
You can answer the hiker\’s question by computing the weight of every possible combination of items that the hiker might pack and then checking each sum against the 42 pounds that the hiker wants to carry. Although simple to describe, the algorithm has high complexity. The number of possible combinations (that is, the number of subsets of all items) is an exponential function of the number of items. Add one item to the hiker\’s collection of gear and you double the number of subsets that you must consider.
(I will fib just a tiny bit in my next calculations because I want to establish a symmetry between this and the previous problem. If you are curious and clever, perhaps you can explain why you would write 31 where I have written 32.)
You must consider 32 combinations if you have 5 items, but 64 combinations if you have 6 items. If you are choosing items from a set of 10 items, you will have to consider 1024 combinations. The number of combinations rises to a million if you have 20 items and to more than a billion if you have 30 items. If the hiker has stored 100 items in his closet, you will have to examine a billion billion trillion possible combinations.
You know that computers are fast. How fast? Can we compute a billion billion trillion sums in the time that God has given us on earth? Industry has increased the speed of computers at a rapid pace and promises continued improvements. How much gain in speed will we need to answer the hiker’s question? Suppose that a genie gave you such a powerful computer. What will you do if a second hiker presents you with 200 pieces of camping gear?
Many problems resemble the hiker\’s problem in the following ways:
- We can describe the problems.
- We can describe algorithms for their solution.
- The times required to solve the problem with any of those known algorithms greatly exceed human lifespans, even on the fastest computers, except when the size of the input is very small.
Stephen Cook and Leonid Levin produced evidence that suggests that solutions to problem’s like the hiker’s problem are forever unattainable. They showed that an efficient solution to one problem in the set would allow an efficient solution to any of the others. Why should this knowledge strengthen our belief that each problem is intrinsically complex?