This chapter deals a lot with very large numbers and especially the problem of exponential explosion of time taken. There are a number of resources around that illustrate these concepts. The video The Power of Exponentials, Big and Small from MIT is downloadable, and illustrates exponential growth with some humorous examples.
12. Complexity and Tractability
Introduction
Are there problems that are too hard even for computers? It turns out that there are. In this chapter we're going to look at problems where it's easy to tell the computer what to do – by writing a program – but the computer can’t do what we want because it takes far too long: millions of centuries, perhaps. Not much good buying a faster computer either: if it were a hundred times faster it would still take millions of years; even one a million times faster would take hundreds of years. That's what you call a hard problem – one where it takes far longer than the lifetime of the fastest computer imaginable to produce a solution!
Large numbers ahead! Teacher Note
