A brief history of the theory of computation

Somewhere in the beginning of the 20th century,
the notion of a computer was mathematically formalized.
(The name `computer' came from people whose job it was to perform mathematical
computations on a piece of paper - they were called computers)

It was asked first: Is there something a computer can't compute? Even
if it is given an unbounded amount of time and space to use?
Alan Turing showed that even in such a case a computer cannot solve the following problem:
You give it a code of some computer program and ask it: If I run this program will it go
on running forever? Or will it stop after some finite amount of time?
Turing showed that whatever program you write to answer this question, it will always
give the wrong answer on some computer program it gets as input.

But it seemed that pretty much any problem you would want to solve
you could write a computer program for.
So the next big question was: Out of the problems a computer *can* solve, are there problems it can't solve in a reasonable amount of time?
A good way to think of reasonable is : Suppose I give the computer an input to the problem that is 800 bits long. Then if it can solve the problem before the universe ends using just the resources inside the universe
then this is reasonable.

Using the Theory of NP-Completeness it was shown that the following problem probably cannot be solved in a reasonable amount of time:
We have a map with n cities. Between each 2 there is a train. We start in the first city.
We ask what is the fastest way to go through all the cities and return to the first one.
That is, in which way order should we go through the cities to minimize the total travel time.
This problem is called - The Travelling Salesman Problem - or TSP
But, alongside theory who said this problem is hard, on many of the maps and sets of n cities that people cared the problem was and is being solved in practice.
So, now the next big question: Characterize which instances of TSP can be solved in reasonable time and which cannot.
One example - suppose the n cities are located in log(n) different states that are very far away from each other. And furthermore, inside the states it is clear what the best route is. Then we can prove an efficient algorithm exists.