"Forty-two!" yelled Loonquawl. "Is that all you've got to show for seven and a half million years' work?"
"I checked it very thoroughly," said the computer, "and that quite definitely is the answer. I think the problem, to be quite honest with you, is that you've never actually known what the question is."
In Douglas Adams' The Hitchhiker's Guide To The Galaxy, a race of super-intelligent beings constructs a super-intelligent computer called Deep Thought. They then proceed to ask this hypersmart computer the Ultimate Question: What is the meaning of Life, the Universe, and Everything?
The computer replies that this will take a bit of time and quietly goes into compute mode for the next seven and a half million years. Generations perish and suns collapse before the computer announces that it has finally discovered the answer. The answer, it informs the breathless throng of waiting people, is forty-two.
In algorithm theory, there is a class of problems which are known as NP-hard problems. Problems that belong to this class are mathematically intractable; they have no known solution in polynomial time.
Consider the simple task of searching for a given number within a list of unsorted numbers. We might take a brute force approach and sequentially examine each number until we find the desired one. The upper bound in this case is simply the size of the list. Or we could sort the list and successively divide into equal intervals till we find the interval that contains the number. This is called a binary search, and the worst case performance of such a search is log n, base 2. The run times are polynomial functions.
NP-hard problems, on the other hand, have no known solutions in polynomial time. For example, the classic Traveling Salesman problem goes: A salesman has to visit a certain number of cities as part of a sales tour. He starts at his home city, visits each city on the tour and returns to his home city. There is a cost to travelling between each pair of cities. It is cheaper to travel between cities that are closer together than to cities far away. In what order must the salesman visit the cities so that he visits each city exactly once and the total cost of the tour is the least possible? Alternatively stated, the question is that of finding a least cost spanning path through a graph in which the cities are the nodes and the travel costs are the edges.
The TSP is hellishly difficult to solve for even moderately large values of n, the number of cities. The question seems simple, but the solution is hard.
The most fundamental questions that we ask often seem very simple, yet defy satisfactory answers. I remember reading somewhere that biologists are still in disagreement about what exactly constitutes life. Imagine that.
In algorithm theory, there is a class of problems which are known as NP-hard problems. Problems that belong to this class are mathematically intractable; they have no known solution in polynomial time.
Consider the simple task of searching for a given number within a list of unsorted numbers. We might take a brute force approach and sequentially examine each number until we find the desired one. The upper bound in this case is simply the size of the list. Or we could sort the list and successively divide into equal intervals till we find the interval that contains the number. This is called a binary search, and the worst case performance of such a search is log n, base 2. The run times are polynomial functions.
NP-hard problems, on the other hand, have no known solutions in polynomial time. For example, the classic Traveling Salesman problem goes: A salesman has to visit a certain number of cities as part of a sales tour. He starts at his home city, visits each city on the tour and returns to his home city. There is a cost to travelling between each pair of cities. It is cheaper to travel between cities that are closer together than to cities far away. In what order must the salesman visit the cities so that he visits each city exactly once and the total cost of the tour is the least possible? Alternatively stated, the question is that of finding a least cost spanning path through a graph in which the cities are the nodes and the travel costs are the edges.
The TSP is hellishly difficult to solve for even moderately large values of n, the number of cities. The question seems simple, but the solution is hard.
The most fundamental questions that we ask often seem very simple, yet defy satisfactory answers. I remember reading somewhere that biologists are still in disagreement about what exactly constitutes life. Imagine that.
Why is there something instead of nothing?
What is time?
Why can't we reverse entropy? In Isaac Asimov's words, "You can't turn smoke and ash back into a tree."
We are each looking for personal answers to our own fundamental questions. But as Douglas Adams' computer says, maybe we need to find the right question first.
Or maybe not. Who the heck knows. I need an ice-cream.
We are each looking for personal answers to our own fundamental questions. But as Douglas Adams' computer says, maybe we need to find the right question first.
Or maybe not. Who the heck knows. I need an ice-cream.
No comments:
Post a Comment