Overview

In 1971 mathematician Stephen Cook (1939- ) was able to show that a solution to a certain family of computational problems (computer science problems) could not be computed in a reasonable amount of time on even the fastest computers that can exist. He was also able to show that this family of problems was related, so that if a "fast" solution could be found for a single one of them, they could all be solved in the same manner. These problems, called "NP-Complete" problems, turn out to be very important because they deal with optimizing many sorts of activities, including travel itineraries, computer architecture, scheduling, electrical circuits, and more. As a result of the work done by Cook and others, we now have a better idea of problems that are hard...