Douglas Hofstadter says that humans are not known to have a head for numbers (Hofstadter, 1996). For most of us, the numbers 3.2 billion and 5.3 million seem vaguely similar and big. A very popular book (Gamow, 1947) was titled One, Two, Three … Infinity. The author, George Gamow, talks about the Hottentot tribes who had the only numbers one, two, and three in their vocabulary, and beyond that used the word many. Bill Gates is famously reputed to have said, ‘Most people overestimate what they can do in one year and underestimate what they can do in ten years.’

So, how big is big? Why are computer scientists wary of combinatorial growth? In Table 2.1 we looked at the exponential function 2N and the factorial N!, which are respectively the sizes of search spaces for SAT and TSP, with N variables or cities. How long will take it to inspect all the states when N = 50?

For a SAT problem with 50 variables, 250 = 1,125,899,906,842,624. How big is that? Let us say we can inspect a million or 106 nodes a second. We would then need 1,125,899,906.8 seconds, which is about 35.7 years! There are N! = 3.041409320 × 1064 non-distinct tours (each distinct tour has 2N representations) of 50 cities.