Part I Basic Complexity Classes Nab.draft2007-01-0821:59 p0.9(9) Complexity Theory:A Modern Approach.C2006 Sanjeev Arora and Boaz Barak.References and attributions are still incomplete
DRAFT Part I Basic Complexity Classes Web draft 2007-01-08 21:59 Complexity Theory: A Modern Approach. © 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. p0.9 (9)
Chapter 1 The computational model -and why it doesn't matter "The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. The human computer is supposed to be following fired rules;he has no authority to deviate from them in any detail.We may suppose that these rules are supplied in a book,which is altered whenever he is put on to a new job.He has also an unlimited supply of paper on which he does his calculations. Alan Turing,1950 "[Turing/has for the first time succeeded in giving an absolute definition of an in- teresting epistemological notion,i.e.,one not depending on the formalism chosen." Kurt Godel,1946 The previous chapter gave an informal introduction to computation and efficient computations in context of arithmetic.IN this chapter we show a more rigorous and general definition.As mentioned earlier,one of the surprising discoveries of the 1930s was that all known computational models are able to simulate each other.Thus the set of computable problems does not depend upon the computational model. In this book we are interested in issues of computational efficiency,and therefore in classes of "efficiently computable"problems.Here,at first glance,it seems that we have to be very careful about our choice of a computational model,since even a kid knows that whether or not a new video game program is "efficiently computable"depends upon his computer's hardware.Surprisingly though,we can restrict attention to a single abstract computational model for studying many questions about efficiency-the Turing machine.The reason is that the Turing Machine seems able to simulate all physically realizable computational models with very little loss of efficiency.Thus the set of "efficiently computable"problems is at least as large for the Turing Machine as for any other model.(One possible exception is the quantum computer model,but we do not currently know if it is physically realizable.) Nab.draft2007-01-0821:59 pl.1(11) Complexity Theory:A Modern Approach.C2006 Sanjeev Arora and Boaz Barak.References and attributions are still incomplete
DRAFT Chapter 1 The computational model —and why it doesn’t matter “The idea behind digital computers may be explained by saying that these machines are intended to carry out any operations which could be done by a human computer. The human computer is supposed to be following fixed rules; he has no authority to deviate from them in any detail. We may suppose that these rules are supplied in a book, which is altered whenever he is put on to a new job. He has also an unlimited supply of paper on which he does his calculations.” Alan Turing, 1950 “[Turing] has for the first time succeeded in giving an absolute definition of an interesting epistemological notion, i.e., one not depending on the formalism chosen.” Kurt G¨odel, 1946 The previous chapter gave an informal introduction to computation and efficient computations in context of arithmetic. IN this chapter we show a more rigorous and general definition. As mentioned earlier, one of the surprising discoveries of the 1930s was that all known computational models are able to simulate each other. Thus the set of computable problems does not depend upon the computational model. In this book we are interested in issues of computational efficiency, and therefore in classes of “efficiently computable” problems. Here, at first glance, it seems that we have to be very careful about our choice of a computational model, since even a kid knows that whether or not a new video game program is “efficiently computable” depends upon his computer’s hardware. Surprisingly though, we can restrict attention to a single abstract computational model for studying many questions about efficiency—the Turing machine. The reason is that the Turing Machine seems able to simulate all physically realizable computational models with very little loss of efficiency. Thus the set of “efficiently computable” problems is at least as large for the Turing Machine as for any other model. (One possible exception is the quantum computer model, but we do not currently know if it is physically realizable.) Web draft 2007-01-08 21:59 Complexity Theory: A Modern Approach. © 2006 Sanjeev Arora and Boaz Barak. References and attributions are still incomplete. p1.1 (11)
p1.2(12) 1.1.ENCODINGS AND LANGUAGES:SOME CONVENTIONS The Turing machine is a simple embodiment of the age-old intuition that computation consists of applying mechanical rules to manipulate numbers,where the person/machine doing the manip- ulation is allowed a scratch pad on which to write the intermediate results.The Turing Machine can be also viewed as the equivalent of any modern programming language-albeit one with no built-in prohibition about memory size'.In fact,this intuitive understanding of computation will suffice for most of the book and most readers can skip many details of the model on a first reading, returning to them later as needed. The rest of the chapter formally defines the Turing Machine and the notion of running time, which is one measure of computational effort.It also presents the important notion of the universal Turing machine.Section 1.5 introduces a class of "efficiently computable"problems called P (which stands for Polynomial time)and discuss its philosophical significance.The section also points out how throughout the book the definition of the Turing Machine and the class P will be a starting point for definitions of many other models,including nondeterministic,probabilistic and quantum Turing machines,Boolean circuits,parallel computers,decision trees,and communication games. Some of these models are introduced to study arguably realizable modes of physical computation, while others are mainly used to gain insights on Turing machines. 1.1 Encodings and Languages:Some conventions Below we specify some of the notations and conventions used throughout this chapter and this book to represent computational problem.We make use of some notions from discrete math such as strings,sets,functions,tuples,and graphs.All of these notions are reviewed in Appendix ?? 1.1.1 Representing objects as strings In general we study the complexity of computing a function whose input and output are finite strings of bits.(A string of bits is a finite sequence of zeroes and ones.The set of all strings of length n is denoted by {0,1)",while the set of all strings is denoted by {0,1)*=Unz0 {0,1)";see Appendix A.)Note that simple encodings can be used to represent general objects-integers,pairs of integers,graphs,vectors,matrices,etc.-as strings of bits.For example,we can represent an integer as a string using the binary expansion (e.g.,34 is represented as 100010)and a graph as its adjacency matrix (i.e.,an n vertex graph G is represented by an n x n 0/1-valued matrix A such that Ai=1 iff the edge(i,j)is present in G).We will typically avoid dealing explicitly with such low level issues of representation,and will use to denote some canonical(and unspecified) binary representation of the object z.Often we will drop the symbols and simply use z to denote both the object and its representation. Representing pairs and tuples.We use the notation(x,y)to denote the ordered pair consisting of x and y.A canonical representation for (x,y)can be easily obtained from the representations of x and y.For example,we can first encode (y)as the string o#oy over the alphabet IThough the assumption of an infinite memory may seem unrealistic at first,in the complexity setting it is of no consequence since we will restrict the machine to use a finite amount of tape cells for any given input (the number allowed will depend upon the input size). Web draft2007-01-0821:59
DRAFT p1.2 (12) 1.1. ENCODINGS AND LANGUAGES: SOME CONVENTIONS The Turing machine is a simple embodiment of the age-old intuition that computation consists of applying mechanical rules to manipulate numbers, where the person/machine doing the manipulation is allowed a scratch pad on which to write the intermediate results. The Turing Machine can be also viewed as the equivalent of any modern programming language — albeit one with no built-in prohibition about memory size1 . In fact, this intuitive understanding of computation will suffice for most of the book and most readers can skip many details of the model on a first reading, returning to them later as needed. The rest of the chapter formally defines the Turing Machine and the notion of running time, which is one measure of computational effort. It also presents the important notion of the universal Turing machine. Section 1.5 introduces a class of “efficiently computable” problems called P (which stands for Polynomial time) and discuss its philosophical significance. The section also points out how throughout the book the definition of the Turing Machine and the class P will be a starting point for definitions of many other models, including nondeterministic, probabilistic and quantum Turing machines, Boolean circuits, parallel computers, decision trees, and communication games. Some of these models are introduced to study arguably realizable modes of physical computation, while others are mainly used to gain insights on Turing machines. 1.1 Encodings and Languages: Some conventions Below we specify some of the notations and conventions used throughout this chapter and this book to represent computational problem. We make use of some notions from discrete math such as strings, sets, functions, tuples, and graphs. All of these notions are reviewed in Appendix ??. 1.1.1 Representing objects as strings In general we study the complexity of computing a function whose input and output are finite strings of bits. (A string of bits is a finite sequence of zeroes and ones. The set of all strings of length n is denoted by {0, 1} n , while the set of all strings is denoted by {0, 1} ∗ = ∪n≥0 {0, 1} n ; see Appendix A.) Note that simple encodings can be used to represent general objects—integers, pairs of integers, graphs, vectors, matrices, etc.— as strings of bits. For example, we can represent an integer as a string using the binary expansion (e.g., 34 is represented as 100010) and a graph as its adjacency matrix (i.e., an n vertex graph G is represented by an n × n 0/1-valued matrix A such that Ai,j = 1 iff the edge (i, j) is present in G). We will typically avoid dealing explicitly with such low level issues of representation, and will use xxy to denote some canonical (and unspecified) binary representation of the object x. Often we will drop the symbols x y and simply use x to denote both the object and its representation. Representing pairs and tuples. We use the notation hx, yi to denote the ordered pair consisting of x and y. A canonical representation for hx, yi can be easily obtained from the representations of x and y. For example, we can first encode hx, yi as the string xxy ◦ # ◦ xyy over the alphabet 1Though the assumption of an infinite memory may seem unrealistic at first, in the complexity setting it is of no consequence since we will restrict the machine to use a finite amount of tape cells for any given input (the number allowed will depend upon the input size). Web draft 2007-01-08 21:59
1.1.ENCODINGS AND LANGUAGES:SOME CONVENTIONS p1.3(13) 10,1,#}(where o denotes concatenation)and then use the mapping 000,111,#01 to convert this into a string of bits.To reduce notational clutter,instead of (y)we use (y)to denote not only the pair consisting of x and y but also the representation of this pair as a binary string.Similarly,we use (y,z)to denote both the ordered triple consisting of x,y,z and its representation,and use similar notation for 4-tuples,5-tuples etc.. 1.1.2 Decision problems languages An important special case of functions mapping strings to strings is the case of Boolean functions whose output is a single bit.We identify such a function f with the set Lf ={x:f(x)=1}and call such sets languages or decision problems(we use these terms interchangeably).We identify the computational problem of computing f (i.e.,given x compute f(x))with the problem of deciding the language Lf (i.e.,given z,decide whether xLf). EXAMPLE 1.1 By representing the possible invitees to a dinner party with the vertices of a graph having an edge between any two people that can't stand one another,the dinner party computational problem from the introduction becomes the problem of finding a maximum sized independent set (set of vertices not containing any edges)in a given graph.The corresponding language is: INDSET={(G,k):3S∈V(G)s.t.lSl≥k and Vu,v∈S,u元tE(G)} An algorithm to solve this language will tell us,on input a graph G and a number k,whether there exists a conflict-free set of invitees,called an independent set,of size at least k.It is not immediately clear that such an algorithm can be used to actually find such a set,but we will see this is the case in Chapter 2.For now,let's take it on faith that this is a good formalization of this problem. 1.1.3 Big-Oh notation As mentioned above,we will typically measure the computational efficiency algorithm as the number of a basic operations it performs as a function of its input length.That is,the efficiency of an algorithm can be captured by a function T from the set of natural numbers N to itself such that T(n)is equal to the maximum number of basic operations that the algorithm performs on inputs of length n.However,this function is sometimes be overly dependant on the low-level details of our definition of a basic operation.For example,the addition algorithm will take about three times more operations if it uses addition of single digit binary (i.e.,base 2)numbers as a basic operation, as opposed to decimal (i.e.,base 10)numbers.To help us ignore these low level details and focus on the big picture,the following well known notation is very useful: Web draft2007-01-0821:59
DRAFT 1.1. ENCODINGS AND LANGUAGES: SOME CONVENTIONS p1.3 (13) {0, 1, #} (where ◦ denotes concatenation) and then use the mapping 0 7→ 00, 1 7→ 11, # 7→ 01 to convert this into a string of bits. To reduce notational clutter, instead of xhx, yiy we use hx, yi to denote not only the pair consisting of x and y but also the representation of this pair as a binary string. Similarly, we use hx, y, zi to denote both the ordered triple consisting of x, y, z and its representation, and use similar notation for 4-tuples, 5-tuples etc.. 1.1.2 Decision problems / languages An important special case of functions mapping strings to strings is the case of Boolean functions, whose output is a single bit. We identify such a function f with the set Lf = {x : f(x) = 1} and call such sets languages or decision problems (we use these terms interchangeably). We identify the computational problem of computing f (i.e., given x compute f(x)) with the problem of deciding the language Lf (i.e., given x, decide whether x ∈ Lf ). Example 1.1 By representing the possible invitees to a dinner party with the vertices of a graph having an edge between any two people that can’t stand one another, the dinner party computational problem from the introduction becomes the problem of finding a maximum sized independent set (set of vertices not containing any edges) in a given graph. The corresponding language is: INDSET = {hG, ki : ∃S ⊆ V (G) s.t. |S| ≥ k and ∀u, v ∈ S, u v 6∈ E(G)} An algorithm to solve this language will tell us, on input a graph G and a number k, whether there exists a conflict-free set of invitees, called an independent set, of size at least k. It is not immediately clear that such an algorithm can be used to actually find such a set, but we will see this is the case in Chapter 2. For now, let’s take it on faith that this is a good formalization of this problem. 1.1.3 Big-Oh notation As mentioned above, we will typically measure the computational efficiency algorithm as the number of a basic operations it performs as a function of its input length. That is, the efficiency of an algorithm can be captured by a function T from the set of natural numbers N to itself such that T(n) is equal to the maximum number of basic operations that the algorithm performs on inputs of length n. However, this function is sometimes be overly dependant on the low-level details of our definition of a basic operation. For example, the addition algorithm will take about three times more operations if it uses addition of single digit binary (i.e., base 2) numbers as a basic operation, as opposed to decimal (i.e., base 10) numbers. To help us ignore these low level details and focus on the big picture, the following well known notation is very useful: Web draft 2007-01-08 21:59
p1.4(14) 1.2.MODELING COMPUTATION AND EFFICIENCY DEFINITION 1.2 (BIG-OH NOTATION) If f,g are two functions from N to N,then we (1)say that f=O(g)if there exists a constant c such that f(n)<c.g(n)for every sufficiently large n,(2)say that f=(g)if g=O(f),(3)say that f=e(g)is f=O(g)and g=o(f),(4)say that f=o(g)if for every e>0,f(n)<e.g(n) for every sufficiently large n,and (5)say that f=w(g)if g=o(f). To emphasize the input parameter,we often write f(n)=O(g(n))instead of f =O(g),and use similar notation for o,w,e. EXAMPLE 1.3 Here are some examples for use of big-Oh notation: 1.If f(n)=100m logn and g(n)=n2 then we have the relations f=O(g),g=s(f),f=o(g) 9=w(f): 2.If f(n)=100n2+24n+2logn and g(n)=n2 then f=O(g).We will often write this relation as f(n)=O(n2).Note that we also have the relation g=O(f)and hence f =e(g)and g=Θ(f). 3.If f(n)=minfn,106}and g(n)=1 for every n then f=O(g).We use the notation f=O(1) to denote this.Similarly,if h is a function that tends to infinity with n (i.e.,for every c it holds that h(n)>c for n sufficiently large)then we write h=w(1). 4.If f(n)=2n then for every number cN,if g(n)=ne then g=o(f).We sometimes write this as 2"=n(1).Similarly,we also write h(n)=n()to denote the fact that h is bounded from above by some polynomial.That is,there exist a number c >0 such that for sufficiently large n,h(n)≤ne. For more examples and explanations,see any undergraduate algorithms text such as [KT06, CLRS01]or Section 7.1 in Sipser's book [SIP96]. 1.2 Modeling computation and efficiency We start with an informal description of computation.Let f be a function that takes a string of bits (i.e.,a member of the set {0,1}*)and outputs,say,either 0 or 1.Informally speaking,an algorithm for computing f is a set of mechanical rules,such that by following them we can compute f(x)given any input z{0,1)*.The set of rules being followed is fixed (i.e.,the same rules must work for all possible inputs)though each rule in this set may be applied arbitrarily many times. Each rule involves one or more of the following "elementary"operations: 1.Read a bit of the input. Web draft2007-01-0821:59
DRAFT p1.4 (14) 1.2. MODELING COMPUTATION AND EFFICIENCY Definition 1.2 (Big-Oh notation) If f, g are two functions from N to N, then we (1) say that f = O(g) if there exists a constant c such that f(n) ≤ c · g(n) for every sufficiently large n, (2) say that f = Ω(g) if g = O(f), (3) say that f = Θ(g) is f = O(g) and g = O(f), (4) say that f = o(g) if for every > 0, f(n) ≤ · g(n) for every sufficiently large n, and (5) say that f = ω(g) if g = o(f). To emphasize the input parameter, we often write f(n) = O(g(n)) instead of f = O(g), and use similar notation for o, Ω, ω, Θ. Example 1.3 Here are some examples for use of big-Oh notation: 1. If f(n) = 100n log n and g(n) = n 2 then we have the relations f = O(g), g = Ω(f), f = o(g), g = ω(f). 2. If f(n) = 100n 2 + 24n+ 2logn and g(n) = n 2 then f = O(g). We will often write this relation as f(n) = O(n 2 ). Note that we also have the relation g = O(f) and hence f = Θ(g) and g = Θ(f). 3. If f(n) = min{n, 106} and g(n) = 1 for every n then f = O(g). We use the notation f = O(1) to denote this. Similarly, if h is a function that tends to infinity with n (i.e., for every c it holds that h(n) > c for n sufficiently large) then we write h = ω(1). 4. If f(n) = 2n then for every number c ∈ N, if g(n) = n c then g = o(f). We sometimes write this as 2n = n ω(1). Similarly, we also write h(n) = n O(1) to denote the fact that h is bounded from above by some polynomial. That is, there exist a number c > 0 such that for sufficiently large n, h(n) ≤ n c . For more examples and explanations, see any undergraduate algorithms text such as [KT06, CLRS01] or Section 7.1 in Sipser’s book [SIP96]. 1.2 Modeling computation and efficiency We start with an informal description of computation. Let f be a function that takes a string of bits (i.e., a member of the set {0, 1} ∗ ) and outputs, say, either 0 or 1. Informally speaking, an algorithm for computing f is a set of mechanical rules, such that by following them we can compute f(x) given any input x ∈ {0, 1} ∗ . The set of rules being followed is fixed (i.e., the same rules must work for all possible inputs) though each rule in this set may be applied arbitrarily many times. Each rule involves one or more of the following “elementary” operations: 1. Read a bit of the input. Web draft 2007-01-08 21:59