INDUSTRIAL ENGINEERING APPLICATIONS AND PRACTICE: USERS ENCYCLOPEDIA®

COMPUTATIONAL COMPLEXITY

Given an optimization problem, we need an algorithm to solve it. How do we know that an algorithm is a "good" one? A useful measure of performance would be "the rate of growth of the time or space required to solve larger and larger instances of a problem". Therefore, we need a number to measure the size of a problem. One convenient measure is the size of the input data. For example, the size of a machine scheduling problem might be the number of jobs to sequence, n. More precisely, it is "the number of digits in the data of the problem instance when it is encoded in binary form". The time complexity, or the running time of the algorithm, is the "time" needed by the algorithm (e.g., number of elementary operations such as additions and comparisons) expressed as a function of the problem size.

If an optimization algorithm solves, in the worst case, a problem with an input size of n in time cn² for some constant c that is independent of the input size, n, and the other data of the problem instance, then we say the time complexity of (or, the computational effort required by) the algorithm is O(n²), read order n². In general, an algorithm may have the complexity of O(p(n)). If p(·) is a fixed polynomial function in the size of the problem, then that algorithm is said to be polynomially bounded or, in the words of Edmonds, it is a "good" algorithm and the problem is "well solved".

In order to appreciate the importance of polynomial boundedness, consider the following example adapted from a book by Aho, Hopcroft, and Ullman. We have n jobs and 2 identical machines. Each job can be processed in either machine. We would like to assign each job to a machine such that all the jobs are processed as soon as possible. In other words, we would like to minimize the completion time of the job that is processed last. In the literature this problem is referred to as the "minimizing the makespan in identical parallel machines problem" and denoted by P2||C_max. It is also referred to as "the 2-partition problem": you want to partition n numbers into two, such that the sum of the numbers in one partition is as close to the sum in the other as possible. Consider two algorithms: A1 and A2. The first one, A1 lists the n processing times in the decreasing order and assigns the jobs according to this list to the machine with the least amount of work. It may not find the optimal solution, but it is a good heuristic algorithm with a time complexity of O(n log n); order (n log n) being the complexity of sorting n numbers in descending order. A2, on the other hand, explicitly enumerates all possible solutions. Each job has two possibilities for assignment, either to machine one or to machine two. Since there are n jobs, there are 2ⁿ possible assignments, resulting in the time complexity of O(2ⁿ).

Assume that one unit of time on our computer is equal to one millisecond. The maximum problem size, n that can be solved during a specified time period is shown in the following table:

The Maximum Problem Size That Can Be Solved During A Fixed Amount Of Time

Algorithm	Complexity	1 Second	1 Minute	1 Hour
A1	n log n	140	4,893	2.0 × 105
A2	2n	9	15	21

Consider another way of looking at this comparison. Suppose you have only one minute to solve the problem. Using the faster algorithm, A1, you can solve a problem more than 325 times larger than the one you can solve with the slower algorithm, A2.

Computers are becoming faster and faster with each new generation of chips. It is interesting to see how this increase in speed affects the maximum problem size. Suppose that we replace our computer with another one, which is ten times faster than the current one. The increase in the size, n, of the problem that we can solve due to tenfold speed-up is shown below:

Maximum Problem Size

Algorithm	Complexity	Before Speed-up	After Speed-up
A1	n log n	s1	approx. 10 s1for large n
A2	2n	s2	s2 + 3.3

Note that with algorithm A2, the size of the problem that can be solved after tenfold speed-up only increases by three, whereas with algorithm A1, the size increases almost tenfold. For polynomially bounded algorithms, the increase in the speed of computation has a significant effect. But when an algorithm is not polynomially bounded increase in the speed of computers has negligible effect on our ability to solve large problems. Suppose you want to evaluate all possible ways of ordering 50 jobs on a single machine. There are 50 jobs that can be assigned to the first slot on the machine. Once a job is assigned to the first slot, there are 49 jobs remaining, and hence 49 different ways of assigning a job to the second slot, and so on, until you are left with a single job for the last, 50th, slot on the machine. Therefore, there are 50 × 49 × ··· × 1 = 50! possible ways of sequencing 50 jobs on a single machine. This number is greater than 3 × 10⁶⁴. Suppose it takes one operation to evaluate one possible ordering on the machine. With our computer that performs one operation in one millisecond, we can perform 3 × 10¹³ operations per year if we run the computer every second of the 365 days of the year. Thus it will take 10⁴⁹ centuries to evaluate all possible orderings. Suppose we have a million-fold increase in the speed of the computer; now we will need 10⁴³ centuries! That is to say the increase in the speed of computation is not an answer to algorithms that are not polynomially bounded.

Optimization vs. Recognition Problems

To be more precise about these solvability issues, we need some definitions from the theory of NP-completeness. This theory deals with so-called recognition problems. These problems are also referred to as feasibility or decision problems. Given an optimization problem, the corresponding recognition problem, requiring a yes/no answer, can be constructed in the following manner. Suppose we have a minimization problem, Min f(x), then the recognition problem is asking for the existence of a solution x such that f(x) <= z for some threshold value z.

Suppose we have an "oracle" that returns a "yes" or a "no" answer to our recognition problem, then we can solve any "reasonable" minimization problem by consulting the oracle polynomial number of times. This can be justified as follows. It is reasonable to expect that we have a finite lower bound, a, and a finite upper bound, b, for the optimum value of the objective function. That is, the oracle answers with a "no" to the recognition problem with z = a and "yes" to the recognition problem with z = b. Let u = b - a be the initial interval of uncertainty. It is also reasonable to be content with an integer interval of uncertainty and the nearest integer for the optimal objective function value. Apply a bisection search to the interval of uncertainty: ask the oracle the feasibility of z = a + u/2. Depending on a yes or a no answer, the new interval of uncertainty will be either [a, a + u/2] or [a + u/2, b]. Thus, the previous interval of uncertainty has been reduced by a factor of 2 in one iteration. After performing l bisections, the interval of uncertainty is reduced by a factor of 2^l. If we want the final interval of uncertainty to be of length 1, then we have to perform l bisections, where l is given by:

u / 2^l = 1, or
l = log u.
The quantity, log u = log (b - a), though it may be large, is not a function of the problem size. Thus, we can obtain the optimal solution after log u number of calls to the oracle. Therefore, for the purposes of computational complexity, it is sufficient to be concerned with the recognition problems.

Problem Classes

Now we are ready to formally classify problems according to their inherent complexity. Consider the following definitions.

Class P

A recognition problem belongs to Class P if, for any instance of the problem, a "yes" or a "no" answer can be determined by a polynomial algorithm.

Class NP

A recognition problem belongs to Class NP, if the feasibility of a given structure can be checked in polynomial time.

For example, the recognition version of the scheduling of two parallel machines problem is a member of Class NP. If you give me a structure, that is a list of jobs assigned to each machine, and a z, I can, in polynomial time, "check" if maximum of the sums of processing times in each machine is less than or equal to z. But, suppose the problem is a variant of this problem: determine all possible assignments of jobs to two identical machines such that the makespan is less than or equal to z. Then, if you give me, say, two sets of assignments, and claim that they constitute all the assignments whose makespan is less than or equal to z, I can check if those two are feasible, but cannot be sure if they are the all possible assignments, without computing all possible assignments myself, and I don't have a way of doing the latter in polynomial time. Hence, this problem is not a member of Class NP. It follows from the definitions that Class P is a subset of Class NP.

A problem p₁ is reducible to another problem p₂ if for any instance of p₁, an instance of p₂ can be constructed in polynomial time such that solving the instance of p₂ will solve the instance of p₁ as well. The reducibility of p₁ to p₂ implies that p₁ can be considered as a special case of p₂.

Now the final two definitions in our discussion of computational complexity,

NP-Hard

A problem p is called NP-Hard if every problem, p´, in Class NP can be reduced to p.

NP-Complete

A problem p is called NP-Complete if it is NP-Hard and belongs to Class NP.

All of the above implies the following: if a polynomial time algorithm can be found for any NP-Complete problem, then every problem in Class NP can be solved in polynomial time, and thus proving P = NP. But this is very unlikely, NP contains some very difficult combinatorial problems, such as integer programming and many other problems in graph theory, network design, combinatorial mathematics, and computer science which received considerable amount of research without finding any polynomial algorithm for those problems. We know that P is a subset of NP, the major unresolved problem is whether P is a proper subset of NP or P is a equal to NP.

Practical Implications of the Theory

In order to show the NP-Completeness of a problem in NP, one has to reduce a known NP-Complete problem to it. The practical significance of showing the recognition version of an optimization problem to be NP-Complete is that one should not pursue the search for a good optimizing algorithm for such a problem and be content with finding a good approximating (i.e. heuristic) algorithm.

Still the best guide to the theory of NP-Completeness is the book by Garey and Johnson, Computers and Intractability, which contains a list of NP-Complete problems. This list is continually being updated in specific problem areas. For example, the online source for machine scheduling problems is Bruckner & Knust's "Complexity Results of Scheduling Problems". The online source for general optimization problems is Crescenzi & Kann's "Compendium of NP Optimization Problems".

A current list of research report, surveys, and books on computational complexity can be found in "Electronic Colloquim on Computational Complexity".

© Copyright 1999   INTERNATIONAL JOURNAL OF INDUSTRIAL ENGINEERING

Ömer S. Benli
Bilkent University