An Introduction to Complex Systems by Joe Tranquillo

Author:Joe Tranquillo
Language: eng
Format: epub
ISBN: 9783030025892
Publisher: Springer International Publishing

6.6.2 The Halting Problem and Traveling Salesmen

In 1936, while laying down the groundwork for a theory of computation, Turing came across a major problem. When a program is entered into a computer and set in motion, how long will it take to complete? How do we know that the program won’t simply run forever? At the time, there were plenty of programs known that seemed to run forever. Remember that Turing was assuming infinite resources (e.g., the program won’t stop because it consumes too much energy, a user presses an escape key, or other such external ways to stop the program). It is easy to create a simple program that will go into an infinite loop. But for more complex problems one will not know ahead of time if it will ever stop. Turing proved that there is no foolproof way, simply by looking at a program, to know if it will halt or not. This problem is known as the halting problem.

The classic example of a halting problem is the traveling salesman problem. In this scenario we imagine a salesperson who will travel to various cities. The goal is to find the shortest overall pathway that will allow the salesperson to visit each city only once. If we consider five cities, the shortest route can be found by trying all of the options. A quick calculation will show that there are five ways to visit the first city, then four possibilities after that, and so on, resulting in 5! = 120 possible pathways. If we then increase to 20 cities, we find that there is an explosion in the pathways that would need to be checked. Is there any algorithm that can be sure to find the shortest pathway, no matter the number of cities, without trying every single pathway?

It is important to note that when abstracted, the traveling salesman problem is really about navigating any type of network in a way that will visit each node only once. For that reason, it can be applied to all sorts of problems in the real world. In fact, whenever mathematicians, decision scientists, or computer scientists encounter a problem of this sort, they often will call it a traveling salesman problem.

Even more generally we want to know how much worse a problem will become as it scales. Some problems do not become any worse as we scale them. Others are worse but scale linearly. Then there are problems that get worse but in terms of some polynomial. In other words the problem becomes x 2 times worse or perhaps x 5 worse. What can be shown is that the traveling salesman problem gets worse even faster than any polynomial expression. For that reason it is referred to as an NP-hard (for nondeterministic polynomial time) problem. What Turing in fact proved was that problems that are of type P (polynomial time) can be solved algorithmically. But when it came to NP problems, there would be no way to write an algorithm that could do better than simply trying all of the possibilities.

Download

Copyright Disclaimer:
This site does not store any files on its server. We only index and link to content provided by other sites. Please contact the content providers to delete copyright contents if any and email us, we'll remove relevant links or contents immediately.