Algorithms and computational complexity theory

Navigation:  Network and Location Analysis > Introduction to Network and Location Analysis >

Algorithms and computational complexity theory

Previous pageReturn to chapter overviewNext page

Most of the key problems addressed in location and network analysis can be classed as “optimization problems”. As such, they are an important subset of a much broader set of problems. Understanding the computing resources required, in order to achieve solutions of standard optimization and decision-making problems, is extremely important.

In the case of networks, which typically consist of a set of n vertices, V, and m edges, E, the amount of time taken to compute an exact solution as a function of the number of these elements is vital. Typically this information is provided in so-called “big O” notation and is based on the total number of steps involved in the operation and the way in which these steps are processed. This provides a very crude measure of the order (approximate amount) of time and possibly space (memory, disc) required to complete a run of a particular algorithm, notably as the number of steps becomes large. The actual time required for any specific implementation will vary greatly, depending on the quality of the implementation and the size of the problem. As an example if the amount of time is stated as O(nk) where k is some Real number k>0, then the time required grows as a simple power function (or polynomial function) of the number of elements, n, in the problem. This is generally a worst-case scenario. Example polynomial orders include O(n2) and O(nlogn). Examples of non-polynomial order include O(n!) and O(2n). Note that for n>3, ignoring any additional constant multipliers, the following relation holds:

O(logn)<O(n)<O(nlogn)<O(n2)

i.e. typically some polynomial orders involve far fewer operations than others. The same is true for non-polynomial algorithms, where for example O(2n)<<O(n!) for n>3.

Assuming the problem in question can be solved exactly by a well-defined deterministic algorithm in polynomial time, it is said to be of type P. An example of a problem that can be solved in polynomial time is finding the shortest path from a single source point through a planar Euclidean network. Polynomial time algorithms are sometimes denoted using the abbreviation PTAS or PTAs.

It is possible to identify problems for which a given solution can be checked for optimality in polynomial time, but for which no deterministic algorithm can be devised. A non-deterministic algorithm (or computer) would be one that either: (i) guesses the correct solution and then must verify it to check it is correct; or (ii) utilizes a computer that includes an infinite number of processors working in parallel to determine possible solutions that again must be verified. Non-deterministic Polynomial time or NP problems are the class of problems that can only be determined in this manner. It is clear that PNP but as yet the hypothesis P=NP has not been proven or shown to be false (this hypothesis is the subject of one of the seven $1Million Millennium Math Prizes offered by the Clay Mathematics Institute: see http://www.claymath.org/millenium-problems/p-vs-np-problem for more details).

An example of an NP networking problem is that of determining whether a given non-directional network has a simple cycle that contains every vertex. It is clearly easy to check whether the cycle passes through every vertex and is not self-crossing, but it is very difficult to compute a specific instance of such a circuit as n increases. In fact this problem (known as the Hamiltonian Circuit Problem — HCP) is within the class NP. A specific, and even more challenging problem, related to the HCP, is the Traveling Salesman Problem (TSP). In this case one must find an HC for a network where each location may only be visited once and has minimum overall cost (or time/length).

A problem is described as being NP-hard if solving it would enable all problems in the class NP to be solved in polynomial time. Some NP‑hard problems are in the class NP and some are not. Those that are in NP are called NP‑complete (or NP-full). Proving that a specific problem is NP-complete involves first showing that it is a member of the set NP and then finding a problem that is known to be NP‑complete and seeing if one can reduce (re-define/re-work) this problem such that it becomes identical to the problem being considered. For example, to show that the TSP is NP-complete we could proceed as follows: (i) since HCP is known to be NP-complete we could seek to show first that TSP is a member of the set NP; and then (ii) we could seek to show that the HCP is reducible in polynomial time to the TSP. A central result in complexity theory is the proof that every NP-complete problem is inter-changeable with every other one. NP-hard problems that are not NP-complete are considerably harder to solve, since even their solutions cannot be checked in polynomial time, unlike those of NP-complete problems.