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

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

1.2. Basic Definitions 11

Definition 1.7. An oracle Turing machine M for an oracle ] : ~* -+ ~* is

a (deterministic or nondeterministic) Turing machine that has two more states

qo and qa, and a separate tape called oracle tape. The machine M can write

questions v E ~* to the oracle on the oracle tape and then switch to state %.

Then in one step the word v is erased from the tape, an answer f(v) is written

(~ if no answer exists) and the head of the oracle tape is positioned over the first

letter of f(v). Finally, M switches to the state qa.

We now use this definition to construct an infinite number of complexity classes.

We start by defining how oracle Turing machines can be used to define new

complexity classes based on the definitions of :P and Alp.

Definition 1.8. For a class C of languages we denote by 7a(C) (AfT)(C)) the

class of all languages L, such that there is a language H E C so that there is a

polynomiaUy time bounded (nondeterministic) oracle Turin9 machine M H with

oracle H for L.

Definition 1.9. We define Ao := S0 := II0 := 7 ). For any k E N we define

Ak := 7~(~k--1), ~k := AfT~(Zk_l), II~ := co-~k. The classes Ak, ~k, and IIk

form the polynomial hierarchy PT-/:= Uk>~o ~k. The classes Ai, ~i, and Hi are

said to form the i-th level of 7)7-l.

We note that A1 = P, E1 = AfT•, and H1 = co-AfT ) hold. It is believed though

not proven that no two classes of this hierarchy are equal. On the other hand, if

there is an i such that ~i = H~ holds, then for all j > i one gets ~j = IIj = Aj =

Zi- This event is usually referred to as the collapse of the polynomial hierarchy;

it collapses to the i-th level in this case.

We finally define another variant of Turing machines that allows us to introduce

the concept of randomness.

Definition 1.10. A randomized Turing machine M is defined as a nondeter-

ministic Turing machine such that Vq E Q, a E Z there are at most two different

triples (qt, a', m) with (q, a) • (ql, a ~, m) E 6. I] there are two different triples M

chooses each of them with probability 89 There are three disjoint sets of halting

states A, R, D such that computations of M stop if a state from A U R U D is

reached. If the halting state belongs to A (R), M accepts (rejects) the input. If

the halting state belongs to D then M does not make a decision about the input.

For the randomized Turing machine the computation time is declared in anal-

ogy to the deterministic Turing machine and not in the way it is defined for the

nondeterministic Turing machine. Since the computation time depends on the

random choices it is a random variable. While for deterministic and nondeter-

ministic Turing machines where the classes P and A/'P were the only complexity

classes we defined we will define a number of different complexity classes for

randomized Turing machines which can all be found in the following section.

12 Chapter 1. Complexity and Approximation

1.3 Complexity Classes for Randomized Algorithms

The introduction of randomized Turing machines allows us to define appropriate

complexity classes for these kind of computation; we will follow Wegener [Weg93]

in this section. There are many different ways in which a randomized Turing

machine may behave that may make us say "it solves a problem". According to

this variety of choice there is a variety of complexity classes.

Definition 1.11. The class 7)7 ) (probabilistic polynomial time) consists of all

languages L for which a polynomially time bounded randomized Turing machine

ML exists that for all inputs w E L accepts and for all inputs w ~ L rejects with

probability strictly more than 89 respectively.

7)7)-algorithms are called Monte Carlo algorithms.

Definition 1.12. The class B7)7) (probabilistic polynomial time with bounded

error) consists of all languages L E 7)7) ]or which a constant ~ exists so that

a polynomially time bounded Turing machine ML for L exists that accepts all

inputs w E L and rejects all inputs w ~ L with probability strictly more than

1_ + ~ respectively.

Obviously, BPP is a subset of PP. Assume there are a/)/)-algorithm A1 and

a B7)7)-algorithm A2 for a language L. Our aim is to increase the reliability

of these algorithms, that means to increase the probability of computing the

correct result. We try to clarify the difference in the definitions by considering

an input w of length [w[ for the B7)7)-algorithm A2 first. There is a constant e

such that the probability that A2 computes the correct result is p > 89 + E. For

the input w we use A2 to create a more reliable algorithm by running A2 on w

for t times (t odd) and accept if and only if A2 accepted at least [~1 times.

The probability that A2 gives the correct answer exactly i times in t runs is

ci = (ti)Pi(1 - p)t-, =(ti) (p(1 _p))i (1 - p)2(89 < (t) (1 _e2)' (1 _e2)89 -i

= (ti) (88 - e 2) 89 It follows that the probability of our new algorithm to give the

correct answer is 1 - ~-~!~J ci > 1 - 2 t-1 (88 - s2) ~ ) 1 - 89 (1 -4e2) ~

So if we want to increase the probability of answering correctly to 1 - 5 we can

2 log 25

run A2 log(l_ds2) times to achieve this. If ~ and ~ are assumed to be constants

the running time is polynomial.

If we do the same thing with the PT)-algorithm A1 we can use the calculations

from above if we manage to find a value for E. For an input w with length [w[

there can be 2 p(lwf) different computation paths each with probability 2 -p(lw[) .

So the probability to give the correct answer for the input w is >i 89 -{- 2 -p([w[).

Notice that ~ is not a constant here, it depends on the length of the input. Since

2 log 26 ~_--2

for -1 < x < 1 we have ln(1 + x) < x we know that log(l_de2) > 2 ~ 9

1.3. Complexity Classes for P~andomized Algorithms 13

Since g-1

grows exponentially with Iw[ we need exponentially many runs of A1

to reduce the error probability to 5.

There exist natural probabilistic algorithms that may make an error in identi-

fying an input that belongs to the language L but are not fooled by inputs not

belonging to L; the well-known equivalence-test for read-once branching pro-

grams of Blum, Chandra, and Wegman [BCW80] is an example. The properties

of these algorithms are captured by the following definition of the class Tr o. Also

the opposite behavior (which is captured by the class co-TCP) is possible for quite

natural algorithms as the well-known randomized primality test by Solovay and

Strassen [SS77] shows.

Definition

1.13.

The class T~P (randomized polynomial time) consists of all

languages L for which a polynomially time bounded randomized Turing machine

ML exists which for all inputs w E L accepts with probability strictly more than

! and for all inputs w ~ L rejects with probability 1.

Obviously, TE/'-algorithms are more powerful than BT)~'-algorithms: repeating

such an algorithm t times results in an algorithms with error probability de-

creased to 2 -t.

The three classes P7 ~, B:P/), and 7-r ~ have in common that they do not rely

essentially on the possibility of halting without making a decision about the

input. A randomized Turing machine

for a decision problem L from one

of these classes can easily be modified in such a way that it always accepts or

rejects whether or not the given input belongs to L. To achieve this it is suffi-

cient to define a Turing machine M~ almost identical to

with some simple

modifications that only affect the states. The set of states without decisions D'

is defined as the empty set. The set of rejecting states R' is defined as R t3 D.

It is obvious that the probability of accepting remains unchanged compared to

ML and the probability of rejecting can only be increased implying that M~ is

still a valid randomized Turing machine for L. We will now introduce an even

more reliable class of algorithms, the so called Las Vegas algorithms which build

the class

ZPP,

where the possibility of not giving an answer at all can not be

removed without changing the definition of the class.

Definition

1.14.

The class ZT)'P (probabilistic polynomial time with zero error)

consists of all languages L ]or which a polynomially time bounded randomized

Turing machine ML exists which for all inputs w E L accepts with probability

strictly more than 89 and rejects with probability O, and for all inputs w ~ L

rejects with probability strictly more than 89 and accepts with probability O.

Clearly, modifying

for a language L from Z:P7 ~ such that halting in a state

from D is interpreted as rejecting is not possible since it can no longer be guar-

anteed that no error is made. If one needs a ZPP-algorithm that always yields

a correct answer and never refuses to decide a small change in the definition

14 Chapter 1. Complexity and Approximation

is needed. In this case we settle with expected polynomially bounded running

time instead of guaranteed polynomially bounded running time. So, if a

ZP7 ~-

algorithm in the sense of Definition 1.14 wants to stop without decision about

the input instead of stopping the algorithm can be started all over again. Since

the probability of not giving an answer is strictly less then 89 the expected num-

ber of runs until receiving an answer is less than two and the expected running

time is obviously polynomially time bounded.

The four different complexity classes for randomized algorithms all agree in

demanding polynomial running time but differ in the probabilities of accepting

and rejecting. For an overview we compare these probabilities in Table 1.1.

class w E L w r L

PP ProD(accept) > 89 ProD(reject) > 89

BT~P ProD(accept) > 89 + e ProD(reject) > 89 +

7~:P ProD(accept) > 89 ProD(reject) = 1

ProD(accept) > 89 ProD(reject) > 89

ZPP

ProD(reject) = 0 ProD(accept) = 0

Table 1.1. Overview of complexity classes for polynomially time bounded ran-

domized algorithms.

In analogy to Definition 1.5 we define ZTIME(/) as a generalization of Z:P:P.

Definition 1.15.

The class

ZTIME(f)

consists of all languages L that have

a randomized Turing machine ML which is O(f) time bounded and which for

all inputs w E L accepts with probability strictly more than 89 and rejects with

probability O, and for all inputs w ~ L rejects with probability strictly more than

! and accepts with probability O.

We close this section with some remarks about the relations between the ran-

domized complexity classes.

Proposition

1.16. P C_ Z:P7 ~ C T~7 ~ C_ B:PT~ C_ 7~7~

Proof.

All the inclusions except for 7~:P C_ B7~7 ~ directly follow from the defini-

tions. Given an 7~7~-algorithm A we immediately get a BT~7~-algorithm for the

same language by running A two times. 9

Proposition 1.17. ~ C_ A/'~

1.3. Complexity Classes for Randomized Algorithms 15

Pro@ A randomized Turing machine ML for L E T~/) may be interpreted

as a nondeterministic Turing machine that accepts if ML does and rejects else.

According to the definition of T~/) there is no accepting computation path for w

L, at least one accepting computation path for w E L, and ML is polynomially

time bounded. 9

Proposition

1.18. Z/)/) : T~/) O co-T~/) C_ Af/) M co-Af/)

Pro@ Clearly, Z/)/) : co-Z/)/) so that Z/)/) C C_ T~7 ~ N co-T~/) is obvious.

Given a language L E T~/) ['1 co-T~/), one can use the algorithms for L and L

to construct a Z/)/)-algorithm for L by simply accepting or rejecting according

to the algorithm that rejects; if both algorithms do no reject then no answer is

given. Finally, T~/) M co-T~/) C_ AlP M co-N/) follows immediately from Proposi-

tion 1.17. 9

Proposition 1.19. (AlP C co-A/)) =~ (Af/) = Z/)/))

Proof. Af/) C_ co-T~/) implies co-Af/) C co-co-T~P : T~/), so we get AfT ~ O

co-fir/) C T~/)N co-T~/) and by Proposition 1.18 this equals ZT~/). Since by

Proposition 1.17 we have 7~/) C_ Af/), Af/) C_ co-T~/) C_ co-H/) holds and Af/) =

co-N/) follows. So altogether we have Alp C_ Z/)/) and since Z/)/) C AfT) is

obvious we have Af/) = Z/)/). 9

Proposition 1.20. Af/) U co-A;/) C_/)/)

Proof. We first show A/':P C_ :PP. Let L E AlP and M a polynomially time

bounded nondeterministic Turing machine for L. We assume without loss of

generality that in each step M has at most two possibilities to proceed and

there is a polynomial p such that M finishes its computation on an input w

after exactly p(iwl) steps. We construct a randomized Turing machine M ~ for

L as follows. We compute a random number r equally distributed between 0

and 2 p(Iwl)+2 - 1 (a binary number with p(Iw[) + 2 bits). If r > 2 p(iwl)+l then

M ~ accepts, in the other case it simulates M on w. Obviously the running time

of M' is polynomially bounded. If w ~ L is given, then M will not accept w

on any computation path. So M t accepts only if r > 2 p(iwl)+i that means with

probability less than 89 If w E L there is at least one computation path on which

M accepts w, so the probability for M ~ to accept w is more than 89 -p(Iwl) +

2P(I~I)+i--I 1.

2p([wl)+ 2 ~

Since co-7)P ----/)/) by definition the proof is complete. 9

We summarize the relations between the different randomized complexity classes

in Figure 1.1 that shows the various inclusions we recognized.

16 Chapter 1. Complexity and Approximation

~ C Np

9 9

Z'P'P

BI~'P

P7 ~

,c', -(_,, - G

co-TeP C co-A/p

Fig. 1.1. Relations between complexity classes for randomized algorithms.

1.4 Optimization and Approximation

It is a natural task in practice to find a minimum or maximum of a given function

since it is almost always desirable to minimize the cost and maximize the gain.

The first obvious consequence of entering the grounds of optimization is that we

are no longer confronted with decision problems. The problems we tackle here

correlate some cost- or value-measure to possible solutions of a problem instance.

Our aim is to find a solution that maximizes the value or minimizes the cost if

we are asked to optimize or to find a solution that is as close as possible to the

actual maximum or minimum if approximation is the task. In this section we

will follow the notations of Bovet and Crescenzi [BC93] and Gaxey and Johnson

[GJ79].

Definition 1.21. An optimization problem is defined by a tuple (I, S, v, goal)

such that I is the set of instances of the problem, S is a function that maps an

instance w E I to all feasible solutions, v is a function that associates a positive

integer to all s E S(w), and goal is either minimization or maximization.

The value of an optimal solution to an instance w is called

OPT(W)

and is the

minimum or maximum of {v(s) I s E S(w)} according to goal.

An optimization problem can be associated with a decision problem in a natural

way.

Definition 1.22. For an optimization problem (I, S, v, goal) the underlying

language is the set {(w,k) I w E S,v(w) <~ k}, if the goal is minimization, and

{(w, k) ] w E S, v(w) >>. k}, if the goal is maximization.

We will define some famous optimization problems which have all in common

that their underlying languages are A/P-compete.

KNAPSACK

Instance: A set V of items with weights defined by w : V -+ N and values

v : V -+ N, a maximal weight W E N.

1.4. Optimization and Approximation 17

Problem: Find a subset of V with weight sum not more than W such that the

sum of the values is maximal.

BINPACKING

Instance." A set V of items with sizes defined by s : V --+ N and a bin size b.

Problem: Find a partition of V that defines subsets such that each subset has

size sum not more than b and has a minimal number of subsets.

We introduce two restrictions of BINPACKING, the first one is a AfT~-complete

decision problem and is called PARTITION.

PARTITION

Instance: A set V of items with sizes defined by s : V --+ N.

Question: Is it possible to partition V into two subsets with equal size sum?

PARTITION can be viewed as BINPACKING with the fixed bin size

(~-,,ev s(v))/2

and the question whether all elements fit in just two bins. The formulation

PARTITION forces the items to be small compared to the size of the bins;

otherwise PARTITION

becomes simple. The second restriction of

BINPACKING

we define forces the items to be large compared to the size of the bins; this

property does not simplify the problem significantly, though.

LARGEPACKING

Instance: A set V of items with sizes defined by s : V --~ N and a bin size b

such that

1/5b <~ s(v) <~ 1/3b

holds for all v e V.

Problem: Find a partition of V that defines subsets such that each subset has

size sum not more than b and has a minimal number of subsets.

MAX3SAT

Instance: A Boolean formula 9 in conjunctive normal form such that each

clauses is a disjunction of up to three literals.

Problem: Find an assignment for 9 that satisfies a maximum number of clauses

simultaneously.

TRAVELINGSALESMANPROBLEM (TsP)

Instance: A graph with G = (V, E) with edge weights defined by c : E --4 N.

Problem: Find a circle in G with IVt edges containing all nodes that has a

minimal sum of weights.

We defined the edge weights to be integers. A special case of the TsP uses points

in the plane as nodes and the distances in Euclidian metric as edge weights. In

this case it is more natural to allow edge weights from 1~. Obtaining an optimal

solution together with the length of an optimal tour may become more difficult

now, since it is not clear how long a representation of the length of an optimal

tour may become. However, if only approximation is the goal like in Chapter 13

this problem does not matter.

A restricted version of the TsP that is a decision problem and still Af:P-complete

is called HAMILTONCIRCUIT.

18 Chapter 1. Complexity and Approximation

HAMILTONCIRCUIT

Instance:

A graph G.

Question:

Is there a circle in G with [V[ edges containing all nodes?

1.4.1 Complexity classes for optimization problems

We will concentrate on optimization problems where the main difficulty is to

find an optimal solution; this rules out all problems where things like testing an

input for syntactic correctness is already a hard problem.

Definition

1.23.

The class AfT'O (AFT' optimization) consists of all optimiza-

tion problems (I, S, v,

goal),

where I is in T', for all inputs w the set of solutions

S(w) is in 79, and v(s) is computable in polynomial time.

It is easy to see that for any optimization problem from

AfPO

the underlying

language is in AfP: to an instance w E I an appropriate solution s of polynomial

length can be guessed and verified in polynomial time by computing

v(s)

and

comparing the value with k.

Definition

1.24.

The class T'O (T" optimization) consists of all optimization

problems from AfT'O which have their underlying language in T'.

Up to now we have defined two different classes of optimization problems without

saying anything about optimization algorithms. An optimization algorithm to

a given optimization problem is an algorithm that computes to any instance a

solution with minimal or maximal value according to goal. For many problems it

is well known that computing an optimal solution is AfP-hard, so we have to ask

for less. Instead of optimization algorithms we start looking for approximation

algorithms, that are algorithms that - given an instance w as input - compute a

solution @ for which the value v(~) should be as close to the optimum OPT(w)

as possible. We will distinguish approximation algorithms by that "distance" to

the optimum and start by defining what we are talking about, exactly.

Definition

1.25.

The

relative error ~

is the relative distance of the value of a

feasible solution ~ for an instance x to the optimum

OPT(x)

and is defined as

Iv(~) - OPT(x)I

OPT(X)

The relative error is always non-negative, it becomes zero when an optimal

solution is found. Notice that for minimization the relative error can be any

non-negative real number while for maximization it is never greater than one.

1.4. Optimization and Approximation 19

Naturally, we are seeking for algorithms that find solutions with small relative

error for all instances.

Another measure that yields numbers of the same range for both, minimization

and maximization problems is the following.

Definition 1.26. The ratio r of a solution ~ to an instance x is defined as

(V(:~) OPT(X)}

r :---- max OPT(x)' v(~) "

By definition it is clear that the ratio of a solution is never smaller than 1 and

the ratio of optimal solutions is 1. There are close relations between ratio r and

relative error s for a solution ~ to an instance x. For minimization problems

= r - 1 holds while for maximization problems we get e : 1 - 1 Now we

associate these measures for single solutions to approximation algorithms since

our aim is to compare different approximation algorithms. As usual in complexity

theory we adopt a kind of worst case perspective.

Definition 1.27. The performance ratio r of an approximation algorithm A is

the infimum of all r ~ such that for all inputs x E I the approximation algorithm

A yields solutions ~c E S(x) with ratio at most r ~.

We will call an approximation algorithm with performance ratio r an r-approxi-

mation (algorithm).

One way to classify approximation problems is by the type of approximation

algorithms they allow. It does not matter whether we use the relative error or

performance ratio as our measure for the algorithms; we concentrate on the

performance ratio here.

Definition 1.28. We say that an optimization problem is approximable/f there

exists an approximation algorithm with polynomial time bound and performance

ratio r for some constant value r. The class of all optimization problems which

are approximable is called AT)X. The class o] all optimization problems which

have polynomially time bounded approximation algorithms with performance ra-

tio

r(Iwl)

are called Jz-A792( if

r(Iwl)

a function in the class Yr. Explicitly,

we denote as log A79X the class of optimization problems that have polynomially

time bounded approximation algorithms with performance ratio log([wl).

Although a specific optimization problem may be approximable in the above

sense the performance ratio that can be found may be much too large for being

helpful in practice. So, we are especially interested in optimization problems

which allow polynomial time approximation algorithms with performance ratio

r for any r > 1. The infimum of all achievable performance ratios is 1 for these

problems.

20 Chapter 1. Complexity and Approximation

Definition 1.29. The class 7)T.AS consists of all optimization problems L such

that for any constant r > 1 there exists an approximation algorithm for L with

running time O(p([w[)) and performance ratio r where p is a polynomial in the

length of the input [w[. We call such approximation algorithms polynomial time

approximation scheme (PTAS).

Having a polynomial time approximation scheme means that we are able to find

a solution with ratio r for any fixed r in polynomial time. However, if we are

interested in very good approximations, we should be sure that the running time

does not depend on the chosen performance ratio r too heavily.

Definition 1.30. The class 3:7)T.AS consists of all optimization problems L

such that]or any r = l+e > 1 there exists an approximation algorithm for L with

running time O(p(Iwl , e-i)) and performance ratio r where p is a polynomial in

both the length of the input Iwl and e-1. We call such approximation algorithms

fully polynomial time approximation scheme (FPTAS).

The classes for optimization problems we defined up to here are related in an

obvious way: it is 7)0 C_ .TT)TA8 C_ 7)TAS c_ A7)X c_ AfT)O. If 7) = AFT), the

classes are all equal, of course. On the other hand, 7 ) ~ AfT ) implies that the

classes are all different. We will name problems that allow the separation of the

classes under the assumption 7 ) ~ A/'P and give an idea of how a proof can be

constructed. KNAPSACK belongs to .TT)T.A8 as Ibarra and Kim proved [IK75]

while its underlying language is AfT)-complete, so we get KNAPSACK

7)(_0. The

underlying language of LARGEPACKING is AfT)-complete in the strong sense (it

remains AfT)-complete when all numbers in the input are bounded in size by

a polynomial in the length of the input), so LARGEPACKING E .T7)T.A8 would

imply 7) = AfT)l. On the other hand, LARGEPACKING has a polynomial approxi-

mation time scheme presented by Karmarkar and Karp [KK82]. In Chapter 2 we

will see an ~-approximation algorithm for MAX3SAT showing that it belongs to

AT)X (see Theorem 2.3). In Chapter 7 we will see that there is no better approxi-

mation algorithm possible so .AT)X ~ 7)T.A,.q follows. Finally, a polynomially time

bounded approximation algorithm for the TRAVELINGSALESMANPROBLEM with

any performance ratio r can be used to construct a polynomially time bounded

algorithm that solves the Alp-complete HAMILTONCIRCUIT exactly.

In order to connect the randomized algorithms from Section 1.3 with the concept

of approximation algorithms we introduce the notion of expected performance

ratio.

Definition 1.31. The expected performance ratio r of a randomized approx-

imation algorithm A is the inJSmum of all r I such that for all instances x the

algorithm A yields solutions ~: such that

1 This connection between very good approximations and AlP-completeness of the

underlying language in the strong sense is the topic of Exercise 1.3.