Contents

Part A: Introduction, measuring the efficiency of algorithms, polynomial and exponential time algorithms

Part B: Recognition problems, the Satisfiability Problem, non-deterministic algorithms

Part C: Classes P and NP, polynomial reductions and transformations, NP-complete problems

Part D: Cook's theorem and implications, some concluding remarks

A1. Introduction

Computational Complexity studies:

• the efficiency of algorithms
• the inherent "difficulty" of problems of practical and/or theoretical importance

A2. Measuring the efficiency of algorithms

Regarding the efficiency of algorithms, the rapid advances in computer technology make physical measures (run-time, memory requirements) irrelevant. A more standardized measure is the number of elementary computer operations it takes to solve the problem in the worst case. Average performance is not safe. There may be particular cases (technically called instances of a problem) that behave much worse than the average and nobody can afford to rely on his/her luck.

The number of elementary operations depends of course on the "size" of the problem data. Sorting 1 billion numbers is quite different from sorting 10 ones, so we express the number of elementary operations (expected in the worst-case scenario) as a function of some characteristic number(s) that suffice to capture the volume of the work to be done. For a sorting algorithm, this number is simply the number n of numbers to be sorted.

Now, suppose an algorithm solves a problem of size n in at most 7n³ + 5n² + 27 operations.

For such functions, we are primarily interested in their rate of growth as n increases. We want to distinguish between mild and "exploding" growth rates, therefore differences as that between 7n³ and n³ are not really important (besides, large differences in the constants do not arise in practice). We can also discard the lower order terms, because at large sizes it is the highest degree that determines the rate of growth.

The end result is that the complexity of this algorithm can be sufficiently described by the function g(n) = n³. Formally, we say that this algorithm is "of order O(n³)". It is also usual to say that this algorithm "takes time O(n³)". This symbolism is a reminder that this function expresses the worst-case behavior at sufficiently large sizes.

Note that for sufficiently large n: logn < n < nlogn < n² < n³ < 2ⁿ

logn is interpreted as base-2 logarithm (it does not really matter, since log₂n = log₁₀n / log₁₀2 and constants are ignored as already mentioned).

This is sometimes stated as: O(logn) < O(n ) < O(nlogn) < O(n²) < O(n³) < O(2ⁿ)

Examples:

1. The Traveling Salesman problem is a well-known problem in Combinatorial Optimization, and a notoriously difficult one to solve exactly. The formulation is very simple though: "Given the coordinates of n cities, find the shortest closed tour which visits each city exactly once". This problem has served as a benchmark for almost every new algorithmic idea and was one of the first optimization problems conjectured and then shown to be NP-complete.

To see an algorithm for this famous problem in action, visit Onno Waalewijn's site and try his TSP Java applet.

A "brute force" approach problem would be a "complete enumeration" scheme:

begin
  input n (number of cities), C(n x n) (non negative integer distance matrix)
  min = sufficiently large number (say, n times the maximum element of C)
  for all possible tours, i.e. cyclic permutations of {1,2,...,n}
     find length of tour
     if length < min then
       min=length, store tour
     endif
  next tour
end

Since there are (n-1)! possible tours, the for ... next loop is executed (n-1)! times, each one requiring time O(n) (the time it takes to find the length of the tour, that is add n integers). Therefore, this algorithm is of order (n-1)! O(n) = O(n!). This is certainly prohibitive. If for example a solution to a 10-city problem can be found in 1 second, increasing the number of cities to 20 would result to time: 20!/10! or about 20,000 years.

Compare this result to the performance of a good approximate algorithm for the same problem, namely Lin's 3-optimal heuristic published in [2]. At every iteration of this algorithm, a tour consists of links between cities. The main idea is to locate at each step a triplet of cities which can be connected in a better (length reducing) way. The algorithm stops when no such triplet can be found. The solution is not guaranteed to be optimal but the time required is O(n³). Now, if a 10-city problem takes 1 second, a 20-city one would require only 7 more seconds.

2. An O(nlogn) sorting algorithm

The following algorithm is based on the observation that a list can be easily sorted if it consists of two individually sorted lists. To sort the n elements of a vector A(1),...,A(n) one would call the following recursive procedure with parameters low=1, high=n:

Procedure mergesort(A,low,high)

input: A(low),A(low+1),...,A(high)
output: same numbers in non-decreasing order

begin
  if low <high then
    mid = [(low+high)/2] ! comment: [] stands for "greater integer smaller than"
    call mergesort(low,mid)
    call mergesort(mid+1,high)
    merge(low,mid,high) ! comment: auxiliary routine to combine the results, takes time O(n)
  endif
end

If the computing time for mergesort is T(n) and that for merge is cn, then:

T(1)=a=constant (the time it takes to call the routine with a single number, do nothing and return), and
T(n)=2T(n/2)+cn, for n>1 (two calls to mergesort and one call to merge)

If n is a power of 2, say n = 2^k:

T(n) = 2T(n/2)+cn = 2(2T(n/4)+cn/2)+cn = 4T(n/4)+2cn = 4(2T(n/8)+cn/4)+2cn = 8T(n/8)+3cn = ... = 2^kT(1)+kcn =an+cnlogn

If n is not a power of 2, it is less than some 2^k, so T(n) is bounded by the above. Therefore T(n)=O(nlogn) for all n.

(For a more detailed description, including an efficient implementation of the auxiliary procedure merge, see [1]).

A3. Polynomial and Exponential time algorithms

Example #1 illustrated a very important point: Algorithms which have a polynomial or sub-polynomial time complexity (that is, they take time O(g(n)) where g(n) is either a polynomial or a function bounded by a polynomial), are practical.

Such algorithms with running times of orders O(logn), O(n ), O(nl2ogn), O(n²), O(n³) etc. are called polynomial-time algorithms.

On the other hand, algorithms with complexities which cannot be bounded by polynomial functions are called exponential-time algorithms. These include "exploding-growth" orders which do not contain exponential factors, like n!.

There are several arguments to support the thesis that “polynomial” is a synonym to practical:

First, polynomial-time algorithms are in a much better position to exploit technological advancements which result to increases in computers speed. This can be better shown in the following table:

Time complexity function	Size of Largest Problem Instance solvable in 1 Hour
	With present computer	With computer 100 times faster	With computer 1000 times faster
n	N1	100N1	1000N1
n2	N2	10 N2	31.6 N2
n3	N3	4.64 N3	10 N3
2n	N4	N4+6.64	N4+9.97
3n	N5	N5+4.19	N5+6.29

For example, in the O(2ⁿ) case:
present computer runs for a2ⁿ secs, 1hr = a2^N4 ,
100 times faster computer runs for a2ⁿ/100 secs, 1hr = a2^Nx /100,  therefore
100 2^N4 = 2^Nx, Nx = N4+(log100/log2) = N4+6.64

That is, the effect of improved technology is multiplicative in polynomial-time algorithms and only additive in exponential-time algorithms. The situation is much worse than that shown in the table if complexities involve factorials. In example #1, if an algorithm of order O(n!) solves a 300-city problem in the maximum time allowed, increasing the computation speed by 1000 will not even enable solution of problems with 302 cities in the same time.

A second argument is that, polynomial-time algorithms, once they are discovered, undergo a series of improvements, that is, reductions in the constants in their complexity functions and the degree itself. This is an empirical result and partly explains why complexities like O(n⁸⁰) or O(10¹⁰⁰n) do not appear in practice. Polynomial-time algorithms have typically a degree about 2 or 3, and do not involve extremely large coefficients. The real breakthrough for the solution of a problem is in finding the first polynomial-time algorithm. For combinatorial problems, the "jump" to the polynomial class usually requires a deep insight into the nature of the problem (if this jump can be made at all).

There are, of course, exceptions to these rules. The most famous case is the excellent performance of the Simplex method for Linear Programming which has always worked very well in practice, although it is provably exponential (there are artificial "pathological" cases where Simplex shows its hidden exponential behavior). It might be that the method captures some significant property of the problem which has yet to be discovered.

The general conclusion however is that a problem can be considered "efficiently solved" when a polynomial-time algorithm has been found for it.

Some examples of optimization problems which are considered "well solved" in that sense:

• Linear Programming (polynomial algorithms do exist)
• some Shortest Path problems
• some Longest Path problems (for example simple PERT/CPM calculations)
• the Shortest Spanning Tree problem
• some network flow problems
• Matching problems
• Transportation, Assignment and Transshipment problems
• several special cases of "hard" problems

References

1. E. Horowitz and S. Sahni (1978) "Fundamentals of Computer Algorithms", Pitman, London
2. S. Lin (1965) "Computer Solutions of the Traveling Salesman Problems", BSTJ 44 (10), 2245-2269
3. C. Papadimitriou and K. Steiglitz (1982) "Combinatorial Optimization; Algorithms and Complexity", Prentice-Hall, New Jersey

Part A: Introduction, measuring the efficiency of algorithms, polynomial and exponential time algorithms

Part B: Recognition problems, the Satisfiability Problem, non-deterministic algorithms

Part C: Classes P and NP, polynomial reductions and transformations, NP-complete problems

Part D: Cook's theorem and implications, some concluding remarks

   Special Subjects   Main Page