122

CS240 Part III: Complexity theory

Introduction

In part I of the course we saw that some problems are algorithmically unsolvable. Eg:
? the halting problem (will a given TM halt on a given input?) ? deciding the truth of an arbitrary statement about arithmetic. But there are wide variations in difficulty amongst the solvable problems. In practice it's no use to know that a problem is solvable, if all solutions take an inordinately long time to run. So we need to refine our view of the solvable problems. In part III we will classify them according to difficulty: how long they take to solve. Note: the problems in part III are solvable by an algorithm; but they may not be solvable in a reasonable time.

Earlier, we formalised the notion of a solvable problem as one that can be solved by a Turing machine (Church's thesis). We did this to be able to reason about algorithms in general. We will now formalise the complexity of a problem, in terms of Turing machines, so that we can reason in general about the varying difficulty of problems.
We will classify problems into four levels of difficulty or complexity. (There are many finer divisions).
? The class P of tractable problems that can be solved efficiently (in polynomial time: p-time).
? The intractable problems. Even though these are algorithmically solvable, any algorithmic solution will run in exponential time (or slower) in the worst case. Such problems cannot be solved in a reasonable time, even for quite small inputs, and for practical purposes they are unsolvable for most inputs, unless the algorithm's average case performance is good. The exponential function dwarfs
technological changes (Fig. 6.1), so hardware improvements will not help much.
? The class NP of problems. These form a kind of half-way house between the tractable and intractable problems. They can be solved in p-time, but by a non-deterministic algorithm. Could they have p-time deterministic solutions? This is the famous question ?P=NP?? ? is every NP-problem a P-problem? The answer is thought to be no,

123

though no-one has proved it. So these problems are currently intractable, but haven't been proved so.
? The class NPC of NP-complete problems. In a precise sense, these are the hardest problems in NP. Cook's theorem (?12) shows that NP- complete problems exist (e.g., ?PSAT?); examples include the
Hamiltonian circuit and travelling salesman problems we saw in ?7?8, and around 1,000 others. All NP-complete problems reduce to each other in polynomial time (see ?8.6). So a fast solution to any NP- complete problem would immediately give fast solutions to all the others ? in fact to all NP problems. Because of this, most people believe NP-complete problems have no fast deterministic solution. Why study complexity? It is useful in practice. It guides us towards the tractable problems that are solvable with fast algorithms. Conversely, NP- complete problems occur frequently in applications. Complexity theory tells us that when we meet one, it might be wise not to seek a fast solution, as many have tried to do this without success.
On a more philosophical level, Church's thesis defined an algorithm to be a Turing machine. So two Turing machines that differ even slightly represent two different algorithms. But if each reduces quickly to the other, as all NP-complete problems do, we might wish to regard them as the same algorithm ? even if they solve quite different problems! So the notion of fast reducibility of one problem or algorithm to another gives us a higher-level view of the notion of algorithm.
So in part III we will:
? define the run time function of a Turing machine
? introduce non-deterministic Turing machines and define their run time function also
? formalise fast reduction of one problem to another
? examine NP- and NP-complete problems.

9 Basic complexity theory

We begin by introducing the notions needed to distinguish between tractable and intractable problems. The classes NP and NPC will be discussed in ?10 and ?12.