2.1 Basics

The branch of theoretical computer science known as computational complexity is concerned with classifying problems according to the computational resources required to solve them. Informally, a problem is computationally more complex than a problem if the solution of requires more resources than does the solution of . This informal idea can be turned into a formal theory that touches the very foundations of science (What can be calculated? What can be proven?) as well as practical problems (optimization, cryptography, etc.). This chapter can only provide a short exposition, too short to do justice to the richness and beauty of the theory of computational complexity, but hopefully inspiring enough to whet your appetite for more. For a real understanding of the subject, we recommend (1).

The theory of computational complexity is a mathematical one with precise formal definitions, theorems, and proofs. Here, we will adopt a largely informal point of view. Let us start with a brief discussion of the building blocks of the theory: problems, solutions, and resources.

2.1.1 Problems

Theoretical computer scientists think of a “problem” as an infinite family of problems. Each particular member of this family is called an instance of the problem. Let us illustrate this by an example that dates back to the eighteenth century, wherein the city of Königsberg (now Kaliningrad) seven bridges crossed the river Pregel and its two arms (Figure 2.1). A popular puzzle of the time asked if it was possible to walk through the city crossing each of the bridges exactly once. In theoretical computer science, the “puzzle of the Königsberg bridges” is not considered a problem, but an instance. The corresponding problem is given as follows:

This generalization qualifies as a problem in theoretical computer science since it asks a question on arbitrary graphs, that is, on an infinite set of inputs. It was Leonhard Euler who solved the Königsberg bridges puzzle for general graphs and, en passant, established what is now known as graph theory. In honor of Euler, the problem and the path bear his name. In theoretical computer science, a problem is, to a lesser extent, something that needs to be solved, but an object of mathematical study. We underline this view by writing problem names in elegant small capitals.

2.2 Algorithms and Time Complexity

The running time of an algorithm depends on the problem's size and the specific instance. Sorting 1000 numbers takes longer than sorting 10 numbers, and some algorithms run faster if the input data is partially sorted already. To minimize the dependency on the specific instance, we consider the worst‐case time complexity ,

2.1

where is the running time of the algorithm for input data and the maximum is taken over all problem instances of size . The worst‐case time is an upper bound for the observable running time, which harmonizes with the fact that an algorithm gives an upper bound for the intrinsic complexity of a problem.

A measure of time complexity should be based on a unit of time that is independent of the clock rate of a specific CPU. Such a unit is provided by the time it takes to perform an elementary operation such as the addition of two integer numbers. Measuring the time in this unit means counting the number of elementary operations executed by your algorithm. This number, in turn, depends strongly on the implementation details of the algorithm – smart programmers and optimizing compilers will try to reduce it. Therefore, we will not consider the precise number of elementary operations but only the asymptotic behavior of for large values of as denoted by the Landau symbols and :

• We say is of order at most and write if there exist positive constants and such that for all .
• We say is of order and write if there exist positive constants and such that for all .

Let us apply this measure of complexity to an elementary problem: How fast can you multiply? The algorithm we learned at school takes time to multiply two ‐bit integers. This algorithm is so natural that it is hard to believe that one can do better, but in fact one can.

The idea is to solve the problem recursively by splitting and into high‐order and low‐order terms. First, write

where are ‐bit integers. If we write out in binary, then and are just the first and second halves of its binary digit sequence, respectively, and similarly for . Then

2.2

The grade‐school method of adding two ‐digit numbers takes just time, and, if we operate in binary, it is easy to multiply a number by or simply by shifting it to the left. The hard part of 2.2 then consists of four multiplications of ‐digit numbers, and this gives the recurrence

Unfortunately, the solution to this recurrence is still . So, we need another idea.

The key observation is that we don't actually need four multiplications. Specifically, we don't need and separately; we only need their sum. Now

2.3

Therefore, if we calculate , , and , we can compute by subtracting the first two of these from the third. This changes our recurrence to

2.4

which yields , or roughly .

This divide‐and‐conquer algorithm reduces our upper bound on the intrinsic time complexity of multiplication: before, we knew that this complexity was , and now this is sharpened to . In fact, this algorithm can be improved even further, to for arbitrarily small (3). Thus, multiplication is considerably less complex than the grade‐school algorithm would suggest.

2.3 Tractable Trails: The Class P

Let us return to the problem from the first section. What is the time complexity of EULERIAN PATH? One possible algorithm is an exhaustive (and exhausting) search through all possible paths in a graph, but the intractability of this approach was already noticed by Euler. More than 200 years before the advent of computers, he wrote “The particular problem of the seven bridges of Königsberg could be solved by carefully tabulating all possible paths, thereby ascertaining by inspection which of them, if any, met the requirement. This method of solution, however, is too tedious and too difficult because of the large number of possible combinations, and in other problems where many more bridges are involved it could not be used at all.” (cited from (4)). Euler was, of course, referring to the manual labor in creating an exhaustive list of all possible tours. Today this task can be given to a computer, which will generate and check all tours across the seven bridges in a blink, but Euler's remark is still valid and aims right at the heart of theoretical computer science. Euler addresses the scaling of this approach with the size of the problem. In a graph with many bridges, you have more choices at each node, and these numbers multiply. This leads to an exponential growth of the number of possible tours with the number of edges. The resulting table will soon get too long to be exhaustively searched by even the fastest computer in the world. Solving the “Venice bridges puzzle” (ca. 400 bridges) by exhaustive search would surely overstrain all present‐day computers. But Euler proposed an ingenious shortcut that allows to solve problems much bigger than that.

Euler noticed that in a path that visits each edge exactly once you must leave each vertex on the way via an edge different from the edge that has taken you there. In other words, the degree of the vertex (that is, the number of edges adjacent to the vertex) must be even, except for the vertices where the path starts and ends. This is obviously a necessary condition, but Euler noticed that it is also sufficient:

Euler's theorem allows us to devise an efficient algorithm for EULERIAN PATH: Loop over all vertices of the graph and count the number of odd‐degree vertices. If this number exceeds 2, return “no”, otherwise return “yes”. The precise scaling of the running time depends on the data structure we used to store the graph, but in any case it scales polynomially in the size of the graph.

The enormous difference between exponential and polynomial scaling is obvious. An exponential algorithm means a hard limit for the accessible problem size. Suppose that with your current equipment you can solve a problem of size just within your schedule. If your algorithm has complexity , a problem of size will need twice the time, pushing you definitely off schedule. The increase in time caused by an or algorithm, on the other hand, is far less dramatic and can easily be compensated for by upgrading your hardware. You might argue that a algorithm outperforms a algorithm only for problem sizes that will never occur in your application. A polynomial algorithm for a problem usually goes hand in hand with a mathematical insight into the problem, which lets you find a polynomial algorithm with a small degree, typically with or 3. Polynomial algorithms with are rare and arise in rather esoteric problems.

This brings us to our first complexity class. Given a function , denotes the class of problems for which an algorithm exists that solves problems of size in time . Then, the class P (for polynomial time) is defined as

2.5

In other words, P is the set of problems for which there exists some constant such that there exists an algorithm that solves the problem in time . Conversely, a problem is outside P if no algorithm exists that solves it in polynomial time; for instance, if the most efficient algorithm takes exponential time for some .

For complexity theorists, P is not so much about tractability as it is about whether or not we possess a mathematical insight into a problem's structure. It is trivial to observe that EULERIAN PATH can be solved in exponential time by exhaustive search, but there is something special about EULERIAN PATH that yields a polynomial time algorithm. When we ask whether a problem is in P or not, we are no longer just computer users who want to know whether we can finish a calculation in time to graduate: we are theorists who seek a deep understanding of why some problems are qualitatively easier, or harder, than others.

Thanks to Euler's insight, EULERIAN PATH is a tractable problem. The burghers of Königsberg, on the other hand, had to learn from Euler, that they would never find a walk‐through their hometown crossing each of the seven bridges exactly once.

2.4 Intractable Itineraries: The Class NP

Out next problem is associated with the mathematician and Astronomer Royal of Ireland, Sir William Rowan Hamilton. In 1859, Hamilton put on the market a new puzzle called the Icosian game (Figure 2.2). Its generalization is known as

EULERIAN PATH and HAMILTONIAN PATH have a certain similarity. In the former, we must pass each edge once, whereas in the latter, each vertex once. Both are decision problems, that is, problems with answer “yes” or “no”, and both problems can be solved by exhaustive search, for which both problems would take exponential time. Despite this resemblance, the two problems represent entirely different degrees of difficulty. The available mathematical insights into HAMILTONIAN PATH provide us neither with a polynomial algorithm nor with a proof that such an algorithm is impossible. HAMILTONIAN PATH is intractable, and nobody knows why.

The situation is well described by the proverbial needle in a haystack scenario. It is hard (exponentially) to find the needle in a haystack although we can easily (polynomially) tell a needle from a blade of hay. The only source of difficulty is the large size of the search space. This feature is shared by many important problems, and it will be the base of our next complexity class. The “needle in a haystack” class is called NP for nondeterministic polynomial:

What is nondeterministic time? It is the time consumed by a nondeterministic algorithm, which is like an ordinary algorithm, except that it may use one additional, very powerful instruction:

goto both label 1, label 2

This instruction splits the computation into two parallel processes, one continuing from each of the instructions indicated by “label 1” and “label 2”. By encountering more and more such instructions, the computation will branch like a tree into a number of parallel computations that potentially can grow as an exponential function of the time elapsed (see Figure 2.3). A nondeterministic algorithm can perform an exponential number of computations in polynomial time! In the world of conventional computers, nondeterministic algorithms are a theoretical concept only, but this could change in quantum computing. Solubility by a nondeterministic algorithm means this: All branches of the computation will stop, returning either “yes” or “no”. We say that the overall algorithm returns ‘yes’, if any of its branches returns ‘yes’. The answer is ‘no’, if none of the branches reports ‘yes’. We say that a nondeterministic algorithm solves a decision problem in polynomial time, if the number of steps used by the first of the branches to report ‘yes’ is bounded by a polynomial in the size of the problem.

There are two peculiarities in the definition of NP: First, NP contains only decision problems. This allows us to divide each problem into ‘yes’‐ and ‘no’‐instances. Second, polynomial time is required only for the ‘yes’‐branch of a nondeterministic algorithm (if there is any). This asymmetry between ‘yes’ and ‘no’ reflects the asymmetry between the ‘there is’ and ‘for all’ quantifiers in decision problems: a graph is a ‘yes’‐instance of HAMILTONIAN PATH, if there is at least one Hamiltonian path in . For a ‘no’‐instance, all cycles in have to be non‐Hamiltonian.

Note that the conventional (deterministic) algorithms are special cases of nondeterministic algorithms (those nondeterministic algorithms that do not use the goto both instruction). If we restrict our definition of P to decision problems, we may therefore write .

There is a second, equivalent definition of NP, based on the notion of a succinct certificate. A certificate is a proof. If you claim that a graph has a Hamiltonian path, you can prove your claim by providing a Hamiltonian path, and you can verify your proof in polynomial time. A certificate is succinct, if its size is bounded by a polynomial in the size of the problem. The second definition then reads

It is not hard to see that both definitions are equivalent. The idea is that the path taken by a nondeterministic algorithm to a ‘yes’‐instance is a succinct certificate. And conversely, a succinct certificate can be used to deterministically select the branch in a nondeterministic algorithm that leads to a ‘yes’‐output.

The definition based on nondeterministic algorithms reveals the key feature of the class NP more clearly, but the second definition is more useful for proving that a decision problem is in NP. As an example consider

A certificate of a ‘yes’ instance of COMPOSITENESS is a factorization . It is succinct, because the number of bits in and is less than or equal to the number of bits in , and it can be verified in quadratic time (or even faster, see above) by multiplication. Hence, COMPOSITENESS .

Most decision problems ask for the existence of an object with a given property, like a cycle which is Hamiltonian or a factorization with integer factors. In these cases, the desired object may serve as a succinct certificate. For some problems, this does not work, however, such as for

PRIMALITY is the negation or complement of COMPOSITENESS: the ‘yes’‐instances of the former are the ‘no’‐instances of the latter and vice versa. A succinct certificate for PRIMALITY is by no means obvious. In fact, for many decision problems in NP no succinct certificate is known for the complement, that is, it is not known whether the complement is also in NP. An example is HAMILTONIAN PATH: there is no proof of “non‐Hamiltonicity” that can be verified in polynomial time. This brings us to our next complexity class:

From we get , but is ? In fact, it is, a succinct certificate can be constructed using Fermat's Theorem (5). Euler's Theorem can be used to prove the presence as well as the absence of an Eulerian path, hence . This is generally true for all problems in P: the trace of the polynomial algorithm is a succinct certificate for both ‘yes’‐ and ‘no’‐instances. Hence, we have

2.6

The class NP is populated by many important problems. Let us discuss two of the most prominent members of the class.

2.4.1 Coloring Graphs

Imagine we wish to arrange talks in a conference in such a way that no participant will be forced to miss a talk he/she would like to attend. Assuming an adequate number of lecture rooms enabling us to hold as many parallel talks as we like, can we finish the programme within time slots? This problem can be formulated in terms of graphs: Let be a graph whose vertices are the talks and in which two talks are adjacent (joined by an edge) if and only if there is a participant wishing to attend both. Your task is to assign one of the time slots to each vertex in such a way that adjacent vertices have different time slots. The common formulation of this problem uses colors instead of time slots (Figure 2.4):

Despite its colorful terminology, is a serious problem with a wide range of applications. It arises naturally whenever one is trying to allocate resources in the presence of conflicts, like in our conference example. Another example is the assignment of frequencies to wireless communication devices. We would like to assign one of frequencies to each of devices. If two devices are sufficiently close to each other, they need to use different frequencies to prevent interference. This problem is equivalent to on the graph that has the communication devices as vertices, and an edge for each pair of devices that are close enough to interfere.

If a graph can be colored with less than colors, the proper coloring is a proof of this fact that can be checked in polynomial time, hence . For very few colors, the problem is tractable:

2.7

Finding a polynomial algorithm for this case is left as an exercise. For three or more colors, no polynomial algorithm is known, and exhaustive search through all possible colorings seems to be unavoidable.

2.4.2 Logical Truth

We close this section with a decision problem that is not from graph theory but from Boolean logic. A Boolean variable can take on the value 0 (false) or 1 (true). Boolean variables can be combined in clauses using the Boolean operators

1. – NOT (negation): the clause is true ( ) if and only if is false ( ).
2. – AND (conjunction): the clause is true ( ) if and only if both variables are true: and
3. – OR (disjunction): the clause is true ( ) if and only if at least one of the variables is true: or .

A variable or its negation is called a literal. Different clauses can be combined to yield complex Boolean formulas, e.g.

2.8

A Boolean formula evaluates to either 1 or 0, depending on the assignment of the Boolean variables. In the example above, for , and for . A formula is called satisfiable, if there is at least one assignment of the variables such that the formula is true. is satisfiable,

2.9

is not satisfiable.

Every Boolean formula can be written in conjunctive normal form (CNF) that is, as a set of clauses combined exclusively with the AND‐operator

2.10

where the literals in each clause are combined exclusively with the OR‐operator. The examples and are both written in CNF. Each clause can be considered as a constraint on the variables, and satisfying a formula means satisfying a set of (possibly conflicting) constraints simultaneously. Therefore,

can be considered as prototype of a constraint‐satisfaction problem. Obviously, a Boolean formula for a given assignment of variables can be evaluated in polynomial time, hence . The same is true for the special variant of SAT where one fixes the number of literals per clause:

Again polynomial algorithms are known for and (6), but general SAT and for seem to be intractable.

2.5 Reductions and NP‐Completeness

So far, all the intractable problems seem to be isolated islands in the map of complexity. In fact, they are tightly connected by a device called polynomial reduction, which lets us bound the computational complexity of one problem to that other.

We will illustrate this point by showing that general SAT cannot be harder than 3‐SAT. We write

2.11

which means that the computational complexity of SAT cannot exceed that of 3‐SAT. In other words: if someone finds a polynomial algorithm for 3‐SAT, this would immediately imply a polynomial algorithm for SAT. To prove 2.11, we need to map a general SAT‐formula to a 3‐SAT‐formula such that is satisfiable if and only if is satisfiable. The map proceeds clause by clause. Let be a clause in . If has three literals, it becomes a clause of . If has less than three literals, we fill it up by repeating literals: etc., and copy the augmented clause into . If has more than three literals, with we introduce new variables and form the 3‐SAT‐formula

Now assume that is satisfied. This means that at least one of the literals is true. If we set for and for , all clauses in are satisfied. Now assume that is satisfied and all literals are 0. The first clause in forces to be 1, the second clause then forces to be 1 and so on, but this chain reaction leaves the last clause unsatisfied. Hence is satisfiable if at least one of the literals is 1, which, in turn, implies satisfaction for . Hence, we have proven , and we add to . Obviously, this map from to can be done in polynomial time, hence a polynomial time algorithm for 3‐SAT could be used as a “subroutine” for a polynomial time algorithm for SAT. This proves 2.11.

Since is a special case of SAT, we have and by transitivity

2.12

By a more complicated reduction, one can prove that

2.13

Eqs. 2.12 and 2.13 are reductions from a class of problems to one special member ( ) of that class, but there are also reductions between problems that do not seem a priori to be related to each other, like

2.14

2.15

To prove 2.14, one has to construct a graph for a 3‐SAT‐formula such that is 3‐colorable if and only if is satisfiable, and this construction must not take more than polynomial time. For 2.15, one needs to map a graph in polynomial time to a graph such that is 3‐colorable if and only if has a Hamiltonian path. Reductions like these can be tricky (1), but they reveal an astounding structure within NP. Imagine that after decades of research someone discovers a polynomial time algorithm for HAMILTONIAN PATH. Then the reductions 2.11 2.12 2.13 2.14 2.15 immediately imply polynomial time algorithms for and SAT. And this is only part of the story. Cook (7) revealed polynomial reducibility's true scope in 1971 when he proved the following theorem:

This theorem means that

• No problem in NP is harder than SAT, or SAT is among the hardest problems in NP.
• A polynomial algorithm for SAT would imply a polynomial algorithm for every problem in NP, that is, it would imply .

It seems as if SAT is very special, but according to transitivity and equations 2.11 2.12 2.13 2.14 2.15, it can be replaced by 3‐SAT, 3‐COLORING, or HAMILTONIAN PATH. These problems form a new complexity class:

The class of NP‐complete problems collects the hardest problems in NP. If any of them has an efficient algorithm, then every problem in NP can be solved efficiently, that is, .

Since Cook proved his theorem, many problems have been shown to be NP‐complete. The Web provides a comprehensive, up‐to‐date list of hundreds of NP‐complete problems (8).

2.6 P Versus NP

At this point we will pause for a moment and review what we have achieved. We have defined the class NP whose members represent “needle in a haystack” type of problems. For some of these problems we know a shortcut to locate the needle without actually searching through the haystack. These problems form the subclass P. For other problems, we know that a similar shortcut for one of them would immediately imply shortcuts for all other problems and hence . This is extremely unlikely, however, considered the futile efforts of many brilliant mathematicians to find polynomial time algorithms for the hundreds of NP‐complete problems. The general belief is that . Note that to prove it would suffice to prove the nonexistence of a polynomial time algorithm for a single problem from NP. This would imply the nonexistence of efficient algorithms for all NP‐complete problems. As long as such a proof is missing,

2.17

represents the most famous open conjecture in theoretical computer science. It is one of the seven millennium problems named by the Clay Mathematics Institute, and its solution will be awarded with one million US dollar (9).

Usually, a problem from NP is either found to be in P (by a mathematical insight and a corresponding polynomial time algorithm), or it is classified as NP‐complete (by reducing another NP‐complete problem to it). Every now and then, however, a problem in NP resists classification in P or NP‐complete. COMPOSITENESS and PRIMALITY for example have been proven to be in P only very recently (10). The related problem of factoring an integer in its prime factors can be formulated as a decision problem :

Note that the conventional version of the integer factorization problem (find a nontrivial factor) can be solved in polynomial time if and only if . This follows from the fact that instances of FACTORIZATION with properly chosen thresholds (bisection method) are sufficient to find a nontrivial factor of . Despite many efforts, no polynomial time algorithm for FACTORIZATION has been found. On the other hand, there is no proof that FACTORIZATION is NP‐complete, and the general belief is that it is not. FACTORIZATION seems to lie in the gap between P and NP‐complete. The following theorem ( 1,11) guarantees that this gap is populated unless :

This theorem rules out one of three tentative maps of NP (Figure 2.5). Another problem that– according to our present knowledge – lives in the gap between P and NP‐complete is this:

Two graphs are isomorphic if and only if there is a one‐to‐one mapping from the nodes of one graph to the nodes of the other graph that preserves adjacency and nonadjacency.

Both FACTORIZATION and GRAPH ISOMORPHISM are problems of considerable practical as well as theoretical importance. If you discover a polynomial time algorithm for one of them, you will get invitations to many conferences, but you will not shatter the world of computational complexity. The true challenge is to find a polynomial time algorithm for an NP‐complete problem like SAT or HAMILTONIAN PATH. The consequences of would be far greater than better algorithms for practical problems.

First of all, cryptography, as we know, it would not exist. Modern cryptography relies on the idea of a one‐way function: a function (encryption) that is in P, but whose inverse (decryption) is not. For instance, RSA cryptography (12) relies on the fact that multiplying two numbers is easy, but factoring seems to be hard. However, it is easy to see that finding the inverse of a polynomial time function is in NP. Therefore, if there are no one‐way functions, and we can break any polynomial time encryption scheme. To break the RSA method in particular, however, you “only” need .

Secondly, and most profoundly, if then mathematics would no longer be the same. Consider the problem of finding proofs for the most difficult and elusive mathematical problems. Finding proofs is hard, but checking them is not, as long as they are written in a careful formal language. Indeed, checking a formal proof is just a matter of making sure that each line follows from the previous ones according to the axioms we are working with. The time it takes to do this is clearly polynomial as a function of the length of the proof, so the following problem is in P:

Then the following decision problem is in NP:

Now suppose that . Then you can take your favorite unsolved mathematical problem – the Riemann Hypothesis, the Goldbach Conjecture, you name it – and use your polynomial time algorithm for PROOF EXISTENCE to search for proofs of less than, say, a million lines. The point is that no proof constructed by a human will be longer than a million lines anyway, so if no such proof exists, we have no hope of finding it. In fact, a polynomial algorithm for PROOF EXISTENCE can be used to design a polynomial algorithm that actually outputs the proof (if there is one). If , mathematics could be done by computer. This solution of the P versus NP millennium problem would probably allow you to solve the other six millennium problems, too, and this, in turn, would get you far more than just invitations to conferences.

2.7 Optimization

So far we have classified decision problems. This was mainly for technical reasons, and the notions of polynomial reductions and completeness apply to other problems as well. The most prominent problems are from combinatorial optimization. Here the task is not to find the needle in a haystack, but the shortest (or longest) blade of hay.

As an example consider the following problem from network design. You have a business with several offices and you want to lease phone lines to connect them up with each other. The phone company charges different amounts of money to connect different pairs of cities, and your task is to select a set of lines that connects all your offices with a minimum total cost.

In mathematical terms, the cities and the lines between them form the vertices and edges of a weighted graph , the weight of an edge being the leasing costs of the corresponding phone line. Your task is to find a subgraph that connects all vertices in the graph, that is, a spanning subgraph, and whose edges have minimum total weight. Your subgraph should not contain cycles, since you can always remove an edge from a cycle keeping all nodes connected and reducing the cost. A graph without cycles is a tree, so what you are looking for is a minimum spanning tree in a weighted graph (Figure 2.6).

How do you find a minimum spanning tree? A naive approach is to generate all possible trees with vertices and keep the one with minimal weight. The enumeration of all trees can be done using Prüfer codes (13), but Cayley's formula tells us that there are different trees with vertices. Already for there are more trees than atoms in the observable universe! Hence, exhaustive enumeration is prohibitive for all but the smallest trees. The mathematical insight that turns MST into a tractable problem is this:

The theorem allows us to grow a minimum spanning tree edge by edge, using Prim's algorithm, for example:

The precise time complexity of Prim's algorithm depends on the data structure used to organize the edges, but in any case is an upper bound. (See (14) for faster algorithms.) Equipped with such a polynomial algorithm you can find minimum spanning trees with thousands of nodes within seconds on a personal computer. Compare this to exhaustive search! According to our definition, MST is a tractable problem.

Encouraged by an efficient algorithm for will now investigate a similar problem. Your task is to plan an itinerary for a traveling salesman who must visit cities. You are given a map with all cities and the distances between them. In what order should the salesman visit the cities to minimize the total distance he has to travel? You number the cities arbitrarily and write down the distance matrix , where denotes the distance between city number and city number . A tour is given by a cyclic permutation , where denotes the successor of city , and your problem can be defined as:

TSP is probably is the most famous optimization problem, and there exists a vast literature specially devoted to it, see (15) and references therein. It is not very difficult to find good solutions, even to large problems, but how can we find the best solution for a given instance? There are cyclic permutations, calculating the length of a single tour can be done in time , hence exhaustive search has complexity . Again this approach is limited to very small instances. Is there a mathematical insight that provides us with a shortcut to the optimum solution, like for MST? Nobody knows! Despite the efforts of many brilliant people, no polynomial algorithm for TSP has been found. The situation reminds of the futile efforts to find efficient algorithms for NP‐complete problems, and, in fact, TSP (like many other hard optimization problems) is closely related to NP‐complete decision problems. We will discuss this relation in general terms.

The general instance of an optimization problem is a pair , where is the set of feasible solutions and is a cost function . We consider only combinatorial optimization where the set is countable. A combinatorial optimization problem comes in three different types:

1. The optimization problem : Find the feasible solution that minimizes the cost function.
2. The evaluation problem : Find the cost of the minimum solution.
3. The decision problem : Given a bound , is there a feasible solution such that ?

Under the assumption that the cost function can be evaluated in polynomial time, it is straightforward to write down polynomial reductions that establish

2.18

If the decision variant of an optimization problem is NP‐complete, there is no efficient algorithm for the optimization problem at all – unless .

How does this help us with the TSP? Well, the decision variant of TSP is NP‐complete, as can be seen by the following reduction from HAMILTONIAN PATH. Let be the graph that we want to check for a Hamiltonian path and let denote the vertices and the edges of . We define the distance matrix

2.19

Then has a Hamiltonian path if and only if there is a tour for our salesman of distance strictly less than . If we could check the latter in polynomial time, we would have a polynomial algorithm for HAMILTONIAN PATH, and hence a proof for . Problems like the TSP that are not members of NP but whose polynomial solvability would imply are called NP‐hard.

Now that we have shown TSP to be NP‐hard, we know that a polynomial time algorithm for TSP is rather unlikely to exist, and we better concentrate on polynomial algorithms that yield a good, but not necessarily the best tour.

What about the reverse direction? If we know that the decision variant of an optimization problem is in P, does this imply a polynomial algorithm for the optimization or evaluation variant? For that we need to prove the reversal of Eq. 2.18,

2.20

can be shown to hold if the cost of the optimum solution's cost is an integer with logarithm bounded by a polynomial in the size of the input. The corresponding polynomial reduction evaluates the optimal cost by asking the question “Is ?” for a sequence of values that approaches , similar to the bisection method to find the zeroes of a function.

There is no general method to prove , but a strategy that often works can be demonstrated for the TSP: Let be the known solution of TSP(E). Replace an arbitrary entry of the distance matrix with a value and solve TSP(E) with this modified distance matrix. If the length of the optimum tour is not affected by this modification, the link does not belong to the optimal tour. Repeating this procedure for different links, one can reconstruct the optimum tour with a polynomial number of calls to a TSP(E)–solver, hence . In that sense would also imply efficient algorithms for the TSP and many other hard optimization problems.

2.8 Complexity Zoo

At the time of writing, the complexity zoo (16) housed 535 complexity classes. We have discussed (or at least briefly mentioned) only five: P, NP, co‐NP, NP‐complete, and NP‐hard. Apparently we have seen only the tip of the iceberg! Some of the other 530 classes refer to space (i.e., memory) rather than time complexity, others classify problems that are neither decision nor optimization problems, like counting problems: how many needles are in this haystack? The most interesting classes, however, are based on different (more powerful?) models of computation, most notably randomized algorithms and, of course, quantum computing. As you will learn in Julia Kempe's lecture on quantum algorithms, there is a quantum algorithm that solves FACTORIZATION in polynomial time, but as you have learned in this lecture this is only a very small step toward the holy grail of computational complexity: a polynomial time quantum algorithm for an NP‐complete problem.

References

1. 1 Moore, C. and Mertens, S. (2011) The Nature of Computation, Oxford University Press, www.nature‐of‐computation.org (accessed 05 November 2017).
2. 2 Euler, L. (1736) Solutio problematis ad geometrian situs pertinentis. Comm. Acad. Sci. Imper. Petropol., 8, 128–140.
3. 3 Schönhage, A. and Strassen, V. (1971) Schnelle Multiplikation grosser Zahlen. Computing, 7, 281–292.
4. 4 Lewis, H.R. and Papadimitriou, C.H. (1978) The efficiency of algorithms. Sci. Am., 238 (1), 96–109.
5. 5 Pratt, V.R. (1975) Every prime has a succinct certificate. SIAM J. Comput., 4, 214–220.
6. 6 Aspvall, B., Plass, M.F., and Tarjan, R.E. (1979) A linear‐time algorithm for testing the truth of certain quantified boolean formulas. Inf. Process. Lett., 8 (3), 121–123.
7. 7 Cook, S. (1971) The complexity of theorem proving procedures. Proceedings of the 3rd Annual ACM Symposium on Theory of Computing, pp. 151–158.
8. 8 Crescenzi, P. and Kann, V. (1736) A Compendium of NP Optimization Problems, https://www.nada.kth.se/viggo/problemlist/compendium.html.
9. 9 Clay Mathematics Institute (1986) Millennium Problems, http://www.claymath.org/millennium (accessed 05 November 2017).
10. 10 Agrawal, M., Kayal, N., and Saxena, N. (2004) PRIMES is in P. Ann. Math., 160 (2), 781–793.
11. 11 Ladner, R.E. (1975) On the structure of polynomial time reducibility. J. ACM, 22, 155–171.
12. 12 Rivest, R., Shamir, A., and Adleman, L. (1978) A method for obtaining digital signatures and public key cryptosystems. Commun. ACM, 21, 120–126.
13. 13 Bollobás, B. (1998) Modern Graph Theory, Graduate Texts in Mathematics, vol. 184, Springer‐Verlag, Berlin.
14. 14 Gabow, H.N., Galil, Z., Spencer, T.H., and Tarjan, R.E. (1986) Efficient algorithms for finding minimum spanning trees in undirected and directed graphs. Combinatorica, 6, 109–122.
15. 15 Applegate, D.L., Bixby, R.E., Chvátal, V., and Cook, W.J. (2007) The Traveling Salesman Problem, Princeton Series in Applied Mathematics, Princeton University Press, Princeton, NJ and Oxford.
16. 16 Aaronson, S., Kuperberg, G., Granade, C., and Russo, V. (1971) Complexity Zoo, https://complexityzoo.uwaterloo.ca (accessed 05 November 2017).