Mayr E.W., Pr?mel H.J., Steger A. (eds.) Lectures on Proof Verification and Approximation Algorithms

Подождите немного. Документ загружается.

Introduction

During the last few years we have seen quite spectacular progress in the area

of approximation algorithms. For several fundamental optimization problems we

now actually know matching upper and lower bounds for their approximability

(by polynomial time algorithms).

Perhaps surprisingly, it turned out that for several of these problems, including

the well-known MAX3SAT,

SETCOVER, MAXCLIQUE,

and

CHROMATICNUMBER,

rather simple and straightforward algorithms already yield the essentially best

possible bound, at least under some widely believed assumptions from complex-

ity theory. The missing step for tightening the gap between upper and lower

bound was the improvement of the lower or non-approximability bound. Here

the progress was initiated by a result in a seemingly unrelated area, namely

a new characterization of the well-known complexity class A/'P. This result is

due to Arora, Lund, Motwani, Sudan, and Szegedy and is based on so-called

probabilistically checkable proofs. While already very surprising and certainly

interesting by itself, this result has given rise to fairly general techniques for de-

riving non-approximability results, and it initiated a large amount of subsequent

work.

On the other hand, as if this so-to-speak "negative" progress had inspired the re-

search community, the last few years have also brought us considerable progress

on the "positive" or algorithmic side. Perhaps the two most spectacular results

in this category are the approximation of MAXCUT using semidefinite program-

ming, by Goemans and Willia.mson, and the development of polynomial time

approximation schemes for various geometric problems, obtained independently

by Arora and Mitchell.

These notes give an essentially self-contained exposition of some of these new

and exciting developments for the interplay between complexity theory and ap-

proximation algorithms. The concepts, methods and results are presented in a

unified way that should provide a smooth introduction to newcomers. In partic-

ular, we expect these notes to be a useful basis for an advanced course or reading

group on probabilistically checkable proofs and approximability.

2 Introduction

Overview and Organization of this Book

To be accessible for people from different backgrounds these notes start with

three introductory chapters. The first chapter provides an introduction to the

world of complexity theory and approximation algorithms, as needed for the sub-

sequent treatment. While most of the notions and results from complexity theory

that axe introduced here are well-known and classical, the part on approximation

algorithms incorporates some very recent results which in fact reshape a number

of definitions and viewpoints. It also includes the proof by Trevisan [Tre97] that

MAX3SAT is .4P•-complete.

The second chapter presents a short introduction to randomized algorithms,

demonstrating their usefulness by showing that an essentially trivial randomized

algorithm for MAXE3SAT (the version of MAX3SAT in which all clauses have

exactly three literals) has expected performance ratio 8/7. Later on, in Chapter 7,

this ratio will be seen to be essentially best possible, assuming 7 ~ ~ Af/).

Concluding the introductory part, the third chapter describes various facets

and techniques of derandomization, a term coined for the process of turning

randomized algorithms into deterministic ones. Amongst other things in this

chapter it is shown that the algorithm for MAxE3SAT is easily derandomized.

Chapters 4 to 10 are devoted to the concept of probabilistically checkable proofs

and the implications for non-approximability. Chapter 4 introduces the so-called

PCP-Theorem, a new characterization of AlP in terms of probabilistically check-

able proofs, and explains why and how they can be used to show non-approxima-

bility results. In particular, the nonexistence of polynomial time approxima-

tion schemes for .AT~A'-complete problems and the non-approximability of MAX-

CLIQUE are

shown in detail. A complete and self-contained proof of the PCP-

Theorem is presented in Chapter 5. Chapter 6 is devoted to the so-called Parallel

Repetition Theorem of Raz [Raz95] which is used heavily in subsequent chapters.

At the 1997 STOC, H~stad [H~s97b] presented an exciting paper showing that

the simple algorithm of Chapter 2 for approximating MAXE3SAT is essentially

best possible. Chapter 7 is devoted to this result of Hs The chapter also

introduces the concept of long codes and a method of analyzing these codes

by means of discrete Fourier transforms. These tools will be reused later in

Chapter 9.

Chapter 8 surveys the new reduction techniques for optimization problems using

gadgets, a notion for the first time formally introduced within the framework of

approximation algorithms by Bellare, Goldreich, and Sudan [BGS95].

MAXCLIQUE cannot be approximated up to a factor of n 1-e unless Af:P = Z7~7 ).

This result, also due to H~stad [H~s96a], is based on a version of the PCP-

Theorem using so-called free bits. This concept, as well as H~stad's result, are

described in Chapter 9.

Introduction 3

As the final installment in this series of optimal non-approximability results,

Chapter 10 presents the result of Feige [Fei96] stating that for SETCOVER. the

approximation factor of In n achieved by a simple greedy algorithm is essentially

best possible unless Af:P C DTIME(n ~176

tog

n)).

The last three chapters of these notes are devoted to new directions in the devel-

opment of approximation algorithms. First, Chapter 11 surveys recent achieve-

ments in constructing approximation algorithms based on semidefinite program-

ming. A generalization of linear programming, semidefinite programming had

been studied before for some time and in various contexts. However, only a few

years ago Goemans and Williamson [GW95] showed how to make use of it in

order to provide good approximation algorithms for several optimization prob-

lems.

While the PCP-Theorem implied that no APX-complete problem can have a

polynomial time approximation scheme unless AfT ~ = 7 ~, it is quite surpris-

ing that many such problems nevertheless do have such approximation schemes

when restricted to (in a certain sense) dense instances. Chapter 12 exemplifies

a very general approach for such dense instances, due to Arora, Karger, and

Karpinski [AKK95a].

The final chapter then presents one of the highlights of the work on approxima-

tion algorithms during recent years. It is the development of polynomial time

approximation schemes for geometrical problems like the Euclidean traveling

salesman problem, independently by Arora [Aro96, Aro97] and Mitchell [Mit96].

Notations and Conventions

Areas as lively and evolving as proof verification and approximation algorithms

naturally do not have a standardized set of definitions and notations. Quite often

the same phrase has a slightly different meaning in different papers, or different

symbols have identical meaning. In these notes, we have striven for uniform

notation and concepts. We have tried to avoid any redefinition of terms, and

thus we sometimes had to choose between two (or more) equally well established

alternatives (e.g., should approximation ratios be taken to always be /> 1, or

1, or depending on the type of approximation problem?).

We have also tried to avoid phrases like "reconsidering the proof of Theorem x

in Chapter y we see that it also shows that ...". Instead, we have attempted to

prove all statements in the form in which they'll be needed later on. We hope

that in this way we have been able to make the arguments easier to follow and

to improve readability of the text.

Finally, we want to explicitly add some disclaimers and an apology. The intention

of these notes certainly is

not

to present a survey, detailed or not, on the

history

of research in proof verification or approximation algorithms. This means, in

4 Introduction

particular, that more often than not only the reference to a paper with the best

bound or complexity is given, omitting an entire sequence of earlier work without

which the final result would appear all but impossible. Of course, numerous

citations and pointers to work that had a major impact in the field are given,

but there are doubtlessly many omissions and erroneous judgments. We therefore

would like to apologize to all those whose work does not receive proper credit in

these notes.

Acknowledgments

This volume, and in particular its timely completion, has only been possible

by the joint effort of all participants. We would like to thank them all. Editing

this volume in its various stages has been a great pleasure. For the numerous

technical details special thanks are due to Katja Wolf for taking care of the

bibliography, Stefan Hougardy for preparing the index, and, last but not least,

to Volker Heun, who really did an excellent job in solving the thousand and more

remaining problems.

1. Introduction to the Theory of Complexity and

Approximation Algorithms

Thomas Jansen*

1.1 Introduction

The aim of this chapter is to give a short introduction to the basic terms and

concepts used in several of the following chapters. All these terms and concepts

are somehow standard knowledge in complexity theory and the theory of op-

timization and approximation. We will give definitions of widely used models

and complexity classes and introduce the results that are most important for

our topic. This chapter is definitely not intended to give an introduction to the

theory of complexity to someone who is unaware of this field of computer sci-

ence, there are several textbooks fulfilling this purpose, see e.g. the books of

Bovet and Crescenzi [BC93], Garey and Johnson [GJ79], Wegener [Weg93], and

Papadimitriou [Pap94]. Instead we wish to repeat the main definitions and the-

orems needed in the following text to establish a theory concerned with the task

of optimization and approximation.

It will turn out that it is sufficient to make use of four different though closely

related machine models, namely the Turing machine and three variants of it:

the nondeterministic Turing machine, the oracle Turing machine, and the ran-

domized Turing machine. The first three models are needed to build a theory

of problems, algorithms and the time complexity of solving problems. The ran-

domized Turing machine is well suited to introduce the concept of randomness

allowing - compared with the other three models - new and quite different types

of algorithms to be constructed.

The task we are originally interested in is optimization; for a given problem we

are seeking a solution that is in some well defined sense optimal. Since it will

turn out that the problem of optimization is too hard to be solved exactly in

many cases we will settle with approximation of these hard problems: we will

be satisfied if we are able to "come near to the optimum" without actually

finding it. Related with the idea of not guaranteeing to find an optimal solution

but one that is not too far away is the idea of building algorithms that do not

guarantee to find a solution but which have the property, that the probability of

finding a solution is not too small. The later chapters will show in detail how the

* This author was supported by the Deutsche Forschungsgemeinschaft (DFG) as part

of the Collaborative Research Center "Computational Intelligence" (SFB 531).

6 Chapter 1. Complexity and Approximation

relationship of these two different concepts can be described. We will introduce

the concept of randomized algorithms that do compute solutions with certain

probabilities. We will establish several different levels of confidence that can be

related with the output of randomized algorithms. Furthermore, we will show

the relationship between solving a problem randomized or deterministically so

it will be clear how far solving a problem probabilistically can be easier than

solving it deterministically.

1.2 Basic Definitions

In order to have well defined notions as bases for the following sections we give

some basic definitions here for very well known concepts like Turing machines and

the classes P and Af:P. We make some special assumptions about the machines

we use which differ from the widely used standard but make some proofs much

easier. All assumptions are easy to fulfill by making some simple modifications

of what may be considered as standard Turing machine.

Definition

1.1. A 2bring machine M is a tuple (Q,s, qa,qr,~,F,5) where Q

denotes a finite set of states, s E Q is the state in which M starts its compu-

tations, qa E Q is the accepting state, qr E Q (different to qJ is the rejecting

state, E is a finite set that builds the input alphabet, F D ~ is a finite set that

defines the tape alphabet and 5 : Q • F -+ Q x F • {L, R, S} is the transition

function.

A Taring machine M can be imagined as a computation unit that has an in-

finitely long tape partitioned into cells each containing exactly one letter from

F. It has a head that is capable of reading exactly one letter from and writing

exactly one letter to the position it is at in the moment; the head can be moved

to the left or to the right one cell (or stay) according to the transition function 5.

The Turing machine M is run on an input w E E* and does its computations in

steps. At each moment the Turing machine is in one state q E Q. At the begin-

ning the tape is filled with a special symbol B E F - ~ (the blank symbol), the

letters of the input w are written on consecutive cells of the tape, and the head

of M is positioned over the first letter of w. At each step it reads the current

symbol a E F and according to (f(q, a) = (q', a', m) it writes a', moves according

to m, and changes its state to q~. The computation stops if M reaches the state

qa or the state qr, and the machine accepts or rejects the input according to the

final state. The computation time is the number of steps until M reaches the

halting state. The Turing machine we defined is deterministic in the following

sense. We know exactly what a Turing machine M will do in the next step if

we are informed about the state it is currently in, the content of the tape and

the position of the head. We call this triple of information a configuration of

M. The start configuration is well defined when the input w is given; since

1.2. Basic Definitions 7

defines exactly what M will do in the next step the next configuration is well

defined and by induction we get for each input w a well defined sequence of

configurations.

A Turing machine is capable of doing more than just accepting or rejecting a

given input. Since it can write to the tape it is possible to use a Turing machine

to compute function values, as well. In this case we consider the symbols that are

written to the tape and that are different to the blank symbol to be the computed

function value if the Turing machine halted in an accepting state. The Turing

machine is a very simple model but it is believed to be capable of computing any

function that is computable in an intuitive sense. This belief is commonly referred

to as the Church-Turing Thesis. What is even more important, it is widely

believed that any function that can be computed efficiently on any reasonable

computer can be computed efficiently by a Turing machine, given that the term

"efficiently" is defined adequately: by "efficiently" we mean in polynomial time

as it is defined in the following definition.

Definition 1.2. We say that a Turing machine M is polynomially time

bounded if there exists a polynomial p such that for an input w the compu-

tation of M on w takes at most p(lw D steps Owl denotes the length of w). The

class 79 (polynomial time) consists of all languages L C_ E* for which there exists

a polynomially time bounded Turing machine ML that accepts all inputs w E L

and rejects all inputs w ~ L,

We identify problems which we wish to be solved by a Turing machine with

languages L C_ E*. We say a Turing machine solves a problem if it accepts

all w E L and rejects all w ~ L if the considered problem is described by L.

Since the answer to an instance w of a problem can either be "yes" or "no" and

nothing else we are dealing with so called decision problems. If we are interested

in getting more complicated answers (computing functions with other values) we

can use Turing machines and consider the output that can be found on the tape

as the result of the computation as mentioned above. By Definition 1.2 we know

that a problem belongs to 7 9 if it can be solved by a deterministic algorithm in

polynomial time. We consider such algorithms to be efficient and do not care

about the degree of the polynomial. This might be a point of view that is too

optimistic in practice; on the other hand we are not much too pessimistic if we

consider problems that are not in 79 not to be solvable in practice in reasonable

time. We explicitly denote two types of superpolynomial running times: we call

a running time of fl (2 n~) for some constant c > 0 an exponential running

time. And we call subexponential but superpolynomial running times of the

type O (n p0~ n)) for a polynomial p quasi-polynomial running times. The class

of all languages which have a Turing machine that is quasi-polynomially time

bounded is denoted by 7 5. Analogous definitions can be made for any class C

that is defined by polynomial running time. The analogous class with quasi-

polynomial running time is called C.

8 Chapter 1. Complexity and Approximation

We can assume without loss of generality that M stops after exactly p(Iwl) steps,

so that Definition 1.2 yields the result that a polynomiaUy time bounded Turing

machine has exactly one well defined sequence of configurations of length exactly

p(Iwl) for an input w E E*.

An important concept in complexity theory is non-determinism. It can be intro-

duced by defining a nondeterministic Turing machine.

Definition 1.3. A nondeterministic Turing machine is defined almost exactly

like a Turing machine except for the transition function 5. For a nondeterministic

Turing machine 5 : (Q • F) • (Q • F • {L, R, S}) is a relation.

The interpretation of Definition 1.3 is the following. For a state q E Q and a letter

a E F there may be several triples (q',a',m); at each step a nondeterministic

Turing machine M may choose any of these triples and proceed according to the

choice. Now we have a well defined start configuration but the successor is not

necessarily unique. So we can visualize the possible configurations as a tree (we

call it computation tree) where the start configuration is the root and halting

configurations are the leaves. We call a path from the root to a leaf in this tree

a computation path. We say that M accepts an input w if and only if there

is at least one computation path with the accepting state at the leaf (which is

called an accepting computation path), and M rejects w if and only if there is

no accepting computation path. We can assume without loss of generality that

each node has degree at most two. The computation time for a nondeterministic

Turing machine on an input w is the length of a shortest accepting computation

path. For w r L the computation time is 0.

Definition 1.4. We say that a nondeterministic Turing machine M is polyno-

mially time bounded if there exists a polynomial p such that for an input w E L

the computation of M on w takes at most p(lwl) steps. We can assume without

loss of generality that M stops after exactly p(iwl) steps if w e L. The class Af79

(nondeterministic polynomial time) consists of all languages L C_ ~* for which a

polynomially time bounded nondeterministic Turing machine exists that accepts

all inputs w E L and rejects all inputs w ~ L.

The choice of polynomial bounded computation time leads to very robust com-

plexity classes; a lot of natural problems can be solved in polynomial time and,

what is more, polynomial computation time on Turing machines corresponds

to polynomial computation time on other computation models and vice versa.

But of course, other functions limiting the computation time are possible, so the

classes 7 9 and Af79 can be viewed as special cases of more general complexity

classes as will be described now.

Definition 1.5. The class DTIME(f) consists of all languages L that have a

Turing machine ML which is O(f) time bounded.

1.2. Basic Definitions 9

The class NTIME(f) consists of all languages L that have a nondeterministic

Turing machine ML which is O(f) time bounded.

As a consequence of Definition 1.5 we get 7 ) = DTIME(poly) = (Jp DTIME(p)

and A/7) = NTIME(poly) = (Jp NTIME(p) for polynomials p.

Nondeterministic Turing machines are obviously at least as powerful as deter-

ministic ones. Any deterministic Turing machine M with a function 5 can be

taken as a nondeterministic Turing machine where 5 is seen as a relation. There-

fore, DTIME(f) _C NTIME(f) holds for all f which implies that 7) _C A/7) holds.

Whether 7) -~ AfT) holds is probably the most famous open question in computer

science; the discussion of this question was the starting point for the theory of

A/7)-completeness based on polynomial reductions which we define next.

Definition

1.6. A problem A C Z* is said to be polynomiaUy reducible to a

problem B C A* (A ~p B) if and only if there exists a function f : E* --+ A*,

computable in polynomial time, such that Vw E E* : w E A r f(w) E B. The

function f is called polynomial reduction.

We call a problem A A/P-hard if and only if all problems B E A/7) are poly-

nomially reducible to A. We call a problem A A/7)-complete if and only if A is

A/P-hard and belongs to A/P.

Obviously, if any A/P-complete problem is in P then P = A/7) follows. On

the other hand, if any A/P-complete problem is provably not in 7), then 7)

A/P follows. There are a lot of problems which are known to be A/P-complete,

for a list see e.g. the book of Garey and Johnson [GJ79]. The historically first

and perhaps most important A/P-complete problem is the satisfiability problem

SAT.

SAT

Instance: A Boolean formula 9 in conjunctive normal form.

Question: Does a satisfying assignment for 4~ exist?

Cook [Coo71] proved that SAT is A/P-complete by showing that for any problem

A E A/7 ) it is possible to code the behavior of the nondeterministic Turing

machine MA for A on an input w in a Boolean formula in conjunctive normal

form 9 such that (~ is satisfiable if and only if MA accepts w. This result is called

Cook's theorem and will be used later in this chapter.

The key idea of the proof is that it is possible to describe the computation of

a nondeterministic Turing machine by a Boolean expression r The first step is

to show that some special assumptions about nondeterministic Turing machines

can be made without loss of generality. We assume that the input alphabet is ~ =

{0, 1}, the tape alphabet is 1 ~ -- {0, 1, B}, the states are Q = {q0,..., qn} with

s --- qo, qa = ql, and qr = q2. Fhrthermore, we assume that M stops on an input

w after exactly p(Iwt) steps for a given polynomial p. Finally, all nondeterministic

10 Chapter 1. Complexity and Approximation

steps are assumed to happen at the beginning of the computation: M starts by

producing a string of 0s and ls of appropriate length by nondeterministic steps.

After this phase all following steps axe deterministic. We define IQI (P(IWl) + 1)

variables

Vq(q,

t), 21F] (p(Iw])+l) 2 variables

vt(c, l, t),

and 2(P(iwl)§ 2 variables

Vh(C,t)

with q E Q, t E (0,... ,p(IwI)},

c E (-p(iwl),...

,p(iwI)}, and/E F. The

interpretation of the variables is the following. The variable

vq(q, ~)

is true iff

M is in state q after step

t, vt(c, l, t)

is true iff the tape at position c contains

the letter l after step t, and

Vh(C,t)

is true iff the head of M is over the cell c

after step t. We want to build a set of clauses such that all clauses can only be

satisfied simultaneously if and only if M accepts the input w. First, we make sure

that the start configuration is defined adequately. Second, we have to make sure

that for each t the Turing machine is in one well defined state, the head has one

well defined position, and each cell contains one well defined letter of F. Third,

we must assure that the configuration after step t is a proper successor of the

configuration after step t - 1. Fourth, we have to state that the final state must

be the accepting state. All conditions are either of the form "after step t exactly

one of the following possibilities is true" or "if A is the case after step t- 1 then B

is the case after step t". For the first type of condition we consider the state of M

after the first step as an example. The clause

vq (qo,

1)V...Vvq

(qn,

1) is satisfiable

if and only if M is in at least one state after the first step. The (n§ 1)n/2 clauses

(~vq(q2,

1)) V

(~vq(qj,

1)) with 0 ~ i ~ j ~ n are only satisfiable simultaneously

if and only if M is in at most one state after the first step; so the 1 + (n + 1)n/2

clauses can only be satisfied together if and only if M is in exactly one state

after step 1. For the second type of condition we only mention that the Boolean

formula "A ~ B" is equivalent to "-~A V B". It is easy to see, how all conditions

of valid computations can be expressed as clauses. Since the sizes of Q and F

are constant it is obvious that there are only polynomially many variables and

that only polynomially many clauses are formulated. So, the reduction can be

computed in polynomial time. Given an assignment ~- that satisfies all clauses

simultaneously we not only know that the Turing machine M accepts the input

w. We know the exact computation of M, too. For problems L E AlP we can

assume that some "proof" for the membership of the input w in L of polynomial

length can be stated such that a deterministic Turing machine can verify this

proof in polynomial time. So, assuming that we use nondeterministic Turing

machines that "guess" a proof of polynomial length nondeterministically and

verify it deterministically in polynomial time implies that - given T - we are

able to reconstruct the proof for the membership of w in L in polynomial time.

For any class C of languages we define co-C as the set of all languages L = (w E

~* I w ~ L} such that L C_ ~* belongs to C. Obviously P = co-/) holds, while

Af:P = co-N/) is widely believed to be false.

We will now introduce another type of Turing machine that can be even more

powerful than the nondeterministic one. We will use the so called oracle Taring

machine to define an infinite number of complexity classes that contain the

classes P and Af:P and put them in a broader context.