Chapter 1

Basic Concepts in Algorithms and Complexity Theory

Vangelis Th. PASCHOS.

1.1. Algorithmic complexity

In algorithmic theory, a problem is a general question to which we wish to find an answer. This question usually has parameters or variables the values of which have yet to be determined. A problem is posed by giving a list of these parameters as well as the properties to which the answer must conform. An instance of a problem is obtained by giving explicit values to each of the parameters of the instanced problem.

An algorithm is a sequence of elementary operations (variable affectation, tests, forks, etc.) that, when given an instance of a problem as input, gives the solution of this problem as output after execution of the final operation.

The two most important parameters for measuring the quality of an algorithm are: its execution time and the memory space that it uses. The first parameter is expressed in terms of the number of instructions necessary to run the algorithm. The use of the number of instructions as a unit of time is justified by the fact that the same program will use the same number of instructions on two different machines but the time taken will vary, depending on the respective speeds of the machines. We generally consider that an instruction equates to an elementary operation, for example an assignment, a test, an addition, a multiplication, a trace, etc. What we call the complexity in time or simply the complexity of an algorithm gives us an indication of the time it will take to solve a problem of a given size. In reality this is a function that associates an order of magnitude1 of the number of instructions necessary for the solution of a given problem with the size of an instance of that problem. The second parameter corresponds to the number of memory units used by the algorithm to solve a problem. The complexity in space is a function that associates an order of magnitude of the number of memory units used for the operations necessary for the solution of a given problem with the size of an instance of that problem.

There are several sets of hypotheses concerning the “standard configuration” that we use as a basis for measuring the complexity of an algorithm. The most commonly used framework is the one known as “worst-case”. Here, the complexity of an algorithm is the number of operations carried out on the instance that represents the worst configuration, amongst those of a fixed size, for its execution; this is the framework used in most of this book. However, it is not the only framework for analyzing the complexity of an algorithm. Another framework often used is “average analysis”. This kind of analysis consists of finding, for a fixed size (of the instance) n, the average execution time of an algorithm on all the instances of size n; we assume that for this analysis the probability of each instance occurring follows a specific distribution pattern. More often than not, this distribution pattern is considered to be uniform. There are three main reasons for the worst-case analysis being used more often than the average analysis. The first is psychological: the worst-case result tells us for certain that the algorithm being analyzed can never have a level of complexity higher than that shown by this analysis; in other words, the result we have obtained gives us an upper bound on the complexity of our algorithm. The second reason is mathematical: results from a worst-case analysis are often easier to obtain than those from an average analysis, which very often requires mathematical tools and more complex analysis. The third reason is “analysis portability”: the validity of an average analysis is limited by the assumptions made about the distribution pattern of the instances; if the assumptions change, then the original analysis is no longer valid.

1.2. Problem complexity

The definition of the complexity of an algorithm can be easily transposed to problems. Informally, the complexity of a problem is equal to the complexity of the best algorithm that solves it (this definition is valid independently of which framework we use).

Let us take a size n and a function f (n). Thus:

We can now specify the following general classes of complexity:

With respect to the classes that we have just defined, we have the following relations: P ⊆ PSPACE ⊆ EXPTIME and P ⊂ EXPTIME. Knowing whether the inclusions of the first relation are strict or not is still an open problem.

Almost all combinatorial optimization problems can be classified, from an algorithmic complexity point of view, into two large categories. Polynomial problems can be solved optimally by algorithms of polynomial complexity, that is in O(nk), where k is a constant independent of n (this is the class P that we have already defined). Non-polynomial problems are those for which the best algorithms (those giving an optimum solution) are of a “super-polynomial” complexity, that is in O(f (n)g (n)), where f and g are increasing functions in n and limn→∞ g (n) = ∞. All these problems contain the class EXPTIME.

The definition of any algorithmic problem (and even more so in the case of any combinatorial optimization problem) comprises two parts. The first gives the instance of the problem, that is the type of its variables (a graph, a set, a logical expression, etc.). The second part gives the type and properties to which the expected solution must conform. In the complexity theory case, algorithmic problems can be classified into three categories:

Decision problems are questions concerning the existence, for a given instance, of a configuration such that this configuration itself, or its value, conforms to certain properties. The solution to a decision problem is an answer to the question associated with the problem. In other words, this solution can be:

Let us consider as an example the conjunctive normal form satisfiability problem, known in the literature as SAT: “Given a set U of n Boolean variables x1, …, xn and a set of m clauses2 C1, …, Cm, is there a model for the expression ϕ = ; i.e. is there an assignment of the values 0 or 1 to the variables such that ϕ = 1?”. For an instance ϕ of this problem, if ϕ allows a model then the solution (the correct answer) is yes, otherwise the solution is no.

Let us now consider the MIN TSP problem, defined as follows: given a complete graph Kn over n vertices for which each edge e ∈ E(Kn) has a value d(e) > 0, we are looking for a Hamiltonian cycle H ⊂ E (a partial closely related graph such that each vertex is of 2 degrees) that minimizes the quantity ∑e∈H d(e). Let us assume that for this problem we have, as well as the complete graph Kn and the vector , costs on the edges Kn of a constant K and that we are looking not to determine the smallest (in terms of total cost) Hamiltonian cycle, but rather to answer the following question: “Does there exist a Hamiltonian cycle of total distance less than or equal to K?”. Here, once more, the solution is either yes if such a cycle exists, or no if it does not.

For optimum value calculation problems, we are looking to calculate the value of the optimum solution (and not the solution itself).

In the case of the MIN TSP for example, the optimum associated value calculation problem comes down to calculating the cost of the smallest Hamiltonian cycle, and not the cycle itself.

Optimization problems, which are naturally of interest to us in this book, are those for which we are looking to establish the best solution amongst those satisfying certain properties given by the very definition of the problem. An optimization problem may be seen as a mathematical program of the...