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 NPCompleteness 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.
Personal reflections, random thoughts, mostly but not exclusively and unintentionally related to Buddhism and the spiritual path. More specifically, a lot of what is written here is influenced by my practice of Vipassana meditation as taught by S.N. Goenka.
Saturday, December 21, 2013
Subscribe to:
Post Comments (Atom)
Blog Archive

▼
2013
(95)

▼
December
(23)
 You feel despair, you feel there is no point in ta...
 Hard to kill this crazy love I have for you, anywh...
 A brief history of the theory of computation
 He was rational, open minded but had the need to b...
 It's spreading like wildfire! A big Israeli coffee...
 Most of the time we take for granted that Technolo...
 It's so exciting how Veganism is getting into the ...
 What if before we were born God told us.. `I am go...
 Something I find it hard to relate to is how peopl...
 I was shocked to discover today that there is no g...
 Two things I have discovered from trying to be glu...
 Did I invent you? Are you just my imagination? It'...
 So sweet, for every taste of you I walk a hundred ...
 What do you do with people in your life that just ...
 I thought today of this analogy: You are stressed ...
 Your brain tricks you,dozens times a day.. in the ...
 Be strong for me, transform for me, so that we can...
 Finally, found a place I enjoy showing tourists in...
 Spiritual wealth
 I'm always wondering about whether stopping to dri...
 Looks like it will take some time for my program t...
 So much he wanted to know, what was in her mind, w...
 He didn't know what to do. He wanted her so much i...

▼
December
(23)
About Me

Ariel Gabizon
 Hi! I am a computer science postdoc. For some reason google is not finding my new homepage so I added a link from this profile
No comments:
Post a Comment