1.4.UNCOMPUTABLE FUNCTIONS. p1.15(25) This high level description can turned into an exact specification of the TMU,though we leave this to the reader.If you are not sure how this can be done,think first of how you would program these steps in your favorite programming language and then try to transform this into a description of a Turing machine..■ REMARK 1.15 It is sometimes useful to consider a variant of the universal TM 4 that gets a number t as an extra input (in addition to x and a),and outputs M(x)if and only if Mo halts on x within t steps (otherwise outputting some special failure symbol).By adding a counter to u,the proof of Theorem 1.13 can be easily modified to give such a universal TM with the same efficiency. 1.4 Uncomputable functions. It may seem "obvious"that every function can be computed,given sufficient time.However,this turns out to be false:there exist functions that cannot be computed within any finite number of steps! THEOREM 1.16 There exists a function UC:{0,1*{0,1)that is not computable by any TM. PROOF:The function UC is defined as follows:for every a E{0,1)*,let M be the TM represented by a.If on input a,M halts within a finite number of steps and outputs 1 then UC(a)is equal to 0,otherwise UC(a)is equal to 1. Suppose for the sake of contradiction that there exists a TM M such that M(a)=UC(a)for every a 10,1*.Then,in particular,M(M)=UC(M).But this is impossible:by the definition of UC,if UC(M)1 then M(M)cannot be equal to 1,and if UC(M)=0 then M(M)cannot be equal to 0.This proof technique is called "diagnoalization",see Figure 1.7. 1.4.1 The Halting Problem One might ask why should we care whether or not the function UC described above is computable- why would anyone want to compute such a contrived function anyway?We now show a more natural uncomputable function.The function HALT takes as input a pair a,x and outputs 1 if and only if the TM Mo represented by a halts on input a within a finite number of steps.This is definitely a function we want to compute:given a computer program and an input we'd certainly like to know if the program is going to enter an infinite loop on this input.Unfortunately,this is not possible, even if we were willing to wait an arbitrary long time: THEOREM 1.17 HALT is not computable by any TM. PROOF:Suppose,for the sake of contradiction,that there was a TM MHALT computing HALT.We will use MHALT to show a TM Muc computing UC,contradicting Theorem 1.16. The TM Muc is simple:on input a,we run MHALr(a,a).If the result is 0(meaning that the machine represented by a does not halt on a)then we output 1.Otherwise,we use the universal Web draft2007-01-0821:59
DRAFT 1.4. UNCOMPUTABLE FUNCTIONS. p1.15 (25) This high level description can turned into an exact specification of the TM U, though we leave this to the reader. If you are not sure how this can be done, think first of how you would program these steps in your favorite programming language and then try to transform this into a description of a Turing machine. Remark 1.15 It is sometimes useful to consider a variant of the universal TM U that gets a number t as an extra input (in addition to x and α), and outputs Mα(x) if and only if Mα halts on x within t steps (otherwise outputting some special failure symbol). By adding a counter to U, the proof of Theorem 1.13 can be easily modified to give such a universal TM with the same efficiency. 1.4 Uncomputable functions. It may seem “obvious” that every function can be computed, given sufficient time. However, this turns out to be false: there exist functions that cannot be computed within any finite number of steps! Theorem 1.16 There exists a function UC : {0, 1} ∗ → {0, 1} that is not computable by any TM. Proof: The function UC is defined as follows: for every α ∈ {0, 1} ∗ , let M be the TM represented by α. If on input α, M halts within a finite number of steps and outputs 1 then UC(α) is equal to 0, otherwise UC(α) is equal to 1. Suppose for the sake of contradiction that there exists a TM M such that M(α) = UC(α) for every α ∈ {0, 1} ∗ . Then, in particular, M( xMy) = UC( xMy). But this is impossible: by the definition of UC, if UC( xMy) = 1 then M( xMy) cannot be equal to 1, and if UC( xMy) = 0 then M( xMy) cannot be equal to 0. This proof technique is called “diagnoalization”, see Figure 1.7. 1.4.1 The Halting Problem One might ask why should we care whether or not the function UC described above is computable— why would anyone want to compute such a contrived function anyway? We now show a more natural uncomputable function. The function HALT takes as input a pair α, x and outputs 1 if and only if the TM Mα represented by α halts on input x within a finite number of steps. This is definitely a function we want to compute: given a computer program and an input we’d certainly like to know if the program is going to enter an infinite loop on this input. Unfortunately, this is not possible, even if we were willing to wait an arbitrary long time: Theorem 1.17 HALT is not computable by any TM. Proof: Suppose, for the sake of contradiction, that there was a TM MHALT computing HALT. We will use MHALT to show a TM MUC computing UC, contradicting Theorem 1.16. The TM MUC is simple: on input α, we run MHALT(α, α). If the result is 0 (meaning that the machine represented by α does not halt on α) then we output 1. Otherwise, we use the universal Web draft 2007-01-08 21:59
p1.16(26) 1.4.UNCOMPUTABLE FUNCTIONS. 01000110 11 001下1 01 0 Mo回 1 0 00 0.1 011 10 M (O y%a网1-Maa创j Figure 1.7:Suppose we order all strings in lexicographic order,and write in a table the value of M()for all strings a,t,where Ma denotes the TM represented by the string a and we use to denote the case that M(r)is not a value in {0,1}or that Me does not halt on input r.Then,UC is defined by "negating"the diagonal of this table,and by its definition it cannot be computed by any TM. TM u to compute M(a),where M is the TM represented by a.If M(a)=0 we output 1,and otherwise we output 1.Note that indeed,under the assumption that MHALr(a,x)outputs within a finite number of steps HALT(o,z),the TM Muc(a)will output UC(a)within a finite number of steps.■ REMARK 1.18 The proof technique employed to show Theorem 1.17-namely showing that HALT is uncomputable by showing an algorithm for UC using a hypothetical algorithm for HALT-is called a reduction. We will see many reductions in this book,often used (as is the case here)to show that a problem B is at least as hard as a problem A,by showing an algorithm that could solve A given a procedure that solves B. There are many other examples for interesting uncomputable (also known as undecidable)func- tions,see Exercise 15.There are even uncomputable functions whose formulation has seemingly nothing to do with Turing machines or algorithms.For example,the following problem cannot be solved in finite time by any TM:given a set of polynomial equations with integer coefficients, find out whether these equations have an integer solution(i.e.,whether there is an assignment of integers to the variables that satisfies the equations).This is known as the problem of solving Diophantine equations,and in 1900 Hilbert mentioned finding such algorithm to solve it(which he presumed to exist)as one of the top 23 open problems in mathematics. For more on computability theory,see the chapter notes and the book's website. DRAF Web draft2007-01-0821:59
DRAFT p1.16 (26) 1.4. UNCOMPUTABLE FUNCTIONS. 0 1 00 01 10 11 ... α .... 0 1 00 01 ... α ... 01 1 * 0 1 0 M0 (α) 1 *1 0 1 * 1 ... * 0 10 0 1 * 1 * 0 01 * 0 M α (0) ... Mα (α) 1-Mα (α) Figure 1.7: Suppose we order all strings in lexicographic order, and write in a table the value of Mα(x) for all strings α, x, where Mα denotes the TM represented by the string α and we use ? to denote the case that Mα(x) is not a value in {0, 1} or that Mα does not halt on input x. Then, UC is defined by “negating” the diagonal of this table, and by its definition it cannot be computed by any TM. TM U to compute M(α), where M is the TM represented by α. If M(α) = 0 we output 1, and otherwise we output 1. Note that indeed, under the assumption that MHALT(α, x) outputs within a finite number of steps HALT(α, x), the TM MUC(α) will output UC(α) within a finite number of steps. Remark 1.18 The proof technique employed to show Theorem 1.17— namely showing that HALT is uncomputable by showing an algorithm for UC using a hypothetical algorithm for HALT— is called a reduction. We will see many reductions in this book, often used (as is the case here) to show that a problem B is at least as hard as a problem A, by showing an algorithm that could solve A given a procedure that solves B. There are many other examples for interesting uncomputable (also known as undecidable) functions, see Exercise 15. There are even uncomputable functions whose formulation has seemingly nothing to do with Turing machines or algorithms. For example, the following problem cannot be solved in finite time by any TM: given a set of polynomial equations with integer coefficients, find out whether these equations have an integer solution (i.e., whether there is an assignment of integers to the variables that satisfies the equations). This is known as the problem of solving Diophantine equations, and in 1900 Hilbert mentioned finding such algorithm to solve it (which he presumed to exist) as one of the top 23 open problems in mathematics. For more on computability theory, see the chapter notes and the book’s website. Web draft 2007-01-08 21:59
1.5.DETERMINISTIC TIME AND THE CLASS P. p1.17(27） 1.5 Deterministic time and the class P. A complerity class is a set of functions that can be computed within a given resource.We will now introduce our first complexity classes.For reasons of technical convenience,throughout most of this book we will pay special attention to Boolean functions (that have one bit output),also known as decision problems or languages.(Recall that we identify a Boolean function f with the language Lf fx f(x)=1).) DEFINITION 1.19 (THE CLASS DTIME.) Let T:N-N be some function.We let DTIME(T(n))be the set of all Boolean (one bit output) functions that are computable in c.T(n)-time for some constant c >0. The following class will serve as our rough approximation for the class of decision problems that are efficiently solvable. DEFINITION 1.20 (THE CLASS P) P=Ue>DTIME(n) Thus,we can phrase the question from the introduction as to whether the dinner party problem has an efficient algorithm as follows:"Is INDSET in P?",where INDSET is the language defined in Example 1.6. 1.5.1 On the philosophical importance of P The class P is felt to capture the notion of decision problems with "feasible"decision procedures. Of course,one may argue whether DTIME(n100)really represents "feasible"computation in the real world.However,in practice,whenever we show that a problem is in P,we usually find an n3 or n5 time algorithm(with reasonable constants),and not an n100 algorithm.(It has also happened a few times that the first polynomial-time algorithm for a problem had high complexity,say n20, but soon somebody simplified it to say an n5 algorithm.) Note that the class P is useful only in a certain context.Turing machines are a poor model if one is designing algorithms that must run in a fraction of a second on the latest PC (in which case one must carefully account for fine details about the hardware).However,if the question is whether any subexponential algorithms exist for say INDSET then even an n20 algorithm would be a fantastic breakthrough. P is also a natural class from the viewpoint of a programmer.Suppose undergraduate program- mers are asked to invent the definition of an "efficient"computation.Presumably,they would agree that a computation that runs in linear or quadratic time is "efficient."Next,since programmers often write programs that call other programs (or subroutines),they might find it natural to con- sider a program "efficient"if it performs only "efficient"computations and calls subroutines that are“efficient”.The notion of“efficiency”obtained turns out to be exactly the class P[Cob64. Web draft2007-01-0821:59
DRAFT 1.5. DETERMINISTIC TIME AND THE CLASS P. p1.17 (27) 1.5 Deterministic time and the class P. A complexity class is a set of functions that can be computed within a given resource. We will now introduce our first complexity classes. For reasons of technical convenience, throughout most of this book we will pay special attention to Boolean functions (that have one bit output), also known as decision problems or languages. (Recall that we identify a Boolean function f with the language Lf = {x : f(x) = 1}.) Definition 1.19 (The class DTIME.) Let T : N → N be some function. We let DTIME(T(n)) be the set of all Boolean (one bit output) functions that are computable in c · T(n)-time for some constant c > 0. The following class will serve as our rough approximation for the class of decision problems that are efficiently solvable. Definition 1.20 (The class P) P = ∪c≥1DTIME(n c ) Thus, we can phrase the question from the introduction as to whether the dinner party problem has an efficient algorithm as follows: “Is INDSET in P?”, where INDSET is the language defined in Example 1.6. 1.5.1 On the philosophical importance of P The class P is felt to capture the notion of decision problems with “feasible” decision procedures. Of course, one may argue whether DTIME(n 100) really represents “feasible” computation in the real world. However, in practice, whenever we show that a problem is in P, we usually find an n 3 or n 5 time algorithm (with reasonable constants), and not an n 100 algorithm. (It has also happened a few times that the first polynomial-time algorithm for a problem had high complexity, say n 20 , but soon somebody simplified it to say an n 5 algorithm.) Note that the class P is useful only in a certain context. Turing machines are a poor model if one is designing algorithms that must run in a fraction of a second on the latest PC (in which case one must carefully account for fine details about the hardware). However, if the question is whether any subexponential algorithms exist for say INDSET then even an n 20 algorithm would be a fantastic breakthrough. P is also a natural class from the viewpoint of a programmer. Suppose undergraduate programmers are asked to invent the definition of an “efficient” computation. Presumably, they would agree that a computation that runs in linear or quadratic time is “efficient.” Next, since programmers often write programs that call other programs (or subroutines), they might find it natural to consider a program “efficient” if it performs only “efficient” computations and calls subroutines that are “efficient”. The notion of “efficiency” obtained turns out to be exactly the class P [Cob64]. Web draft 2007-01-08 21:59
p1.18(28) 1.5.DETERMINISTIC TIME AND THE CLASS P. 1.5.2 Criticisms of P and some efforts to address them Now we address some possible criticisms of the definition of P,and some related complexity classes that address these. Worst-case exact computation is too strict.The definition of P only considers algorithms that compute the function eractly on every possible input.However,not all possible inputs arise in practice(although it's not always easy to characterize the inputs that do).Chapter 15 gives a theoretical treatment of average-case complexity and defines the analogue of P in that context.Sometimes,users are willing to settle for approximate solutions.Chapter 18 contains a rigorous treatment of the complexity of approximation. Other physically realizable models.If we were to make contact with an advanced alien civi- lization,would their class P be any different from the class defined here? Most scientists believe the Church-Turing (CT)thesis,which states that every physically realizable computation device-whether it's silicon-based,DNA-based,neuron-based or using some alien technology-can be simulated by a Turing machine.Thus they believe that the set of computable problems would be the same for aliens as it is for us.(The CT thesis is not a theorem,merely a belief about the nature of the world.) However,when it comes to efficiently computable problems,the situation is less clear.The strong form of the CT thesis says that every physically realizable computation model can be simulated by a TM with polynomial overhead (in other words,t steps on the model can be simulated in te steps on the TM,where c is a constant that depends upon the model). If true,it implies that the class P defined by the aliens will be the same as ours.However, several objections have been made to this strong form. (a)Issue of precision:TM's compute with discrete symbols,whereas physical quantities may be real numbers in R.Thus TM computations may only be able to approximately simulate the real world.Though this issue is not perfectly settled,it seems so far that TMs do not suffer from an inherent handicap.After all,real-life devices suffer from noise,and physical quantities can only be measured up to finite precision.Thus a TM could simulate the real-life device using finite precision.(Note also that we often only care about the most significant bit of the result,namely,a 0/1 answer.) Even so,in Chapter 14 we also consider a modification of the TM model that allows computa- tions in R as a basic operation.The resulting complexity classes have fascinating connections with the usual complexity classes. (b)Use of randomness:The TM as defined is deterministic.If randomness exists in the world,one can conceive of computational models that use a source of random bits (i.e., "coin tosses").Chapter 7 considers Turing Machines that are allowed to also toss coins,and studies the class BPP,that is the analogue of P for those machines.(However,we will see in Chapters 16 and 17 the intriguing possibility that randomized computation may be no more powerful than deterministic computation.) (c)Use of quantum mechanics:A more clever computational model might use some of the counterintuitive features of quantum mechanics.In Chapter 20 we define the class BQP, Web draft2007-01-0821:59
DRAFT p1.18 (28) 1.5. DETERMINISTIC TIME AND THE CLASS P. 1.5.2 Criticisms of P and some efforts to address them Now we address some possible criticisms of the definition of P, and some related complexity classes that address these. Worst-case exact computation is too strict. The definition of P only considers algorithms that compute the function exactly on every possible input. However, not all possible inputs arise in practice (although it’s not always easy to characterize the inputs that do). Chapter 15 gives a theoretical treatment of average-case complexity and defines the analogue of P in that context. Sometimes, users are willing to settle for approximate solutions. Chapter 18 contains a rigorous treatment of the complexity of approximation. Other physically realizable models. If we were to make contact with an advanced alien civilization, would their class P be any different from the class defined here? Most scientists believe the Church-Turing (CT) thesis, which states that every physically realizable computation device— whether it’s silicon-based, DNA-based, neuron-based or using some alien technology— can be simulated by a Turing machine. Thus they believe that the set of computable problems would be the same for aliens as it is for us. (The CT thesis is not a theorem, merely a belief about the nature of the world.) However, when it comes to efficiently computable problems, the situation is less clear. The strong form of the CT thesis says that every physically realizable computation model can be simulated by a TM with polynomial overhead (in other words, t steps on the model can be simulated in t c steps on the TM, where c is a constant that depends upon the model). If true, it implies that the class P defined by the aliens will be the same as ours. However, several objections have been made to this strong form. (a) Issue of precision: TM’s compute with discrete symbols, whereas physical quantities may be real numbers in R. Thus TM computations may only be able to approximately simulate the real world. Though this issue is not perfectly settled, it seems so far that TMs do not suffer from an inherent handicap. After all, real-life devices suffer from noise, and physical quantities can only be measured up to finite precision. Thus a TM could simulate the real-life device using finite precision. (Note also that we often only care about the most significant bit of the result, namely, a 0/1 answer.) Even so, in Chapter 14 we also consider a modification of the TM model that allows computations in R as a basic operation. The resulting complexity classes have fascinating connections with the usual complexity classes. (b) Use of randomness: The TM as defined is deterministic. If randomness exists in the world, one can conceive of computational models that use a source of random bits (i.e., ”coin tosses”). Chapter 7 considers Turing Machines that are allowed to also toss coins, and studies the class BPP, that is the analogue of P for those machines. (However, we will see in Chapters 16 and 17 the intriguing possibility that randomized computation may be no more powerful than deterministic computation.) (c) Use of quantum mechanics: A more clever computational model might use some of the counterintuitive features of quantum mechanics. In Chapter 20 we define the class BQP, Web draft 2007-01-08 21:59
1.5.DETERMINISTIC TIME AND THE CLASS P p1.19(29) that generalizes P in such a way.We will see problems in BQP that are currently not known to be in P.However,currently it is unclear whether the quantum model is truly physically realizable.Even if it is realizable it currently seems only able to efficiently solve only very few "well-structured"problems that are (presumed to be)not in P.Hence insights gained from studying P could still be applied to BQP. (d)Use of other erotic physics,such as string theory.Though an intriguing possibility,it hasn't yet had the same scrutiny as quantum mechanics. Decision problems are too limited.Some computational problems are not easily expressed as decision problems.Indeed,we will introduce several classes in the book to capture tasks such as computing non-Boolean functions,solving search problems,approximating optimization problems,interaction,and more.Yet the framework of decision problems turn out to be surprisingly expressive,and we will often use it in this book. 1.5.3 Edmonds'quote We conclude this section with a quote from Edmonds [Edm65],that in the paper showing a polynomial-time algorithm for the maximum matching problem,explained the meaning of such a result as follows: For practical purposes computational details are vital.However,my purpose is only to show as attractively as I can that there is an efficient algorithm.According to the dictionary,“efficient”means“adequate in operation or performance.”This is roughly the meaning I want in the sense that it is conceivable for marimum matching to have no efficient algorithm. ..There is an obvious finite algorithm,but that algorithm increases in difficulty erpo- nentially with the size of the graph.It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph. ..When the measure of problem-size is reasonable and when the sizes assume values arbitrarily large,an asymptotic estimate of...the order of difficulty of an algorithm is theoretically important.It cannot be rigged by making the algorithm artificially difficult for smaller sizes. ..One can find many classes of problems,besides marimum matching and its general- izations,which have algorithms of exponential order but seemingly none better...For practical purposes the difference between algebraic and erponential order is often more crucial than the difference between finite and non-finite. ..It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion. Many of the best algorithmic idea known today would suffer by such theoretical pedantry. ..However,if only to motivate the search for good,practical algorithms,it is important to realize that it is mathematically sensible even to question their eristence.For one thing the task can then be described in terms of concrete conjectures. Wab.draft2007-01-0821:59
DRAFT 1.5. DETERMINISTIC TIME AND THE CLASS P. p1.19 (29) that generalizes P in such a way. We will see problems in BQP that are currently not known to be in P. However, currently it is unclear whether the quantum model is truly physically realizable. Even if it is realizable it currently seems only able to efficiently solve only very few ”well-structured” problems that are (presumed to be) not in P. Hence insights gained from studying P could still be applied to BQP. (d) Use of other exotic physics, such as string theory. Though an intriguing possibility, it hasn’t yet had the same scrutiny as quantum mechanics. Decision problems are too limited. Some computational problems are not easily expressed as decision problems. Indeed, we will introduce several classes in the book to capture tasks such as computing non-Boolean functions, solving search problems, approximating optimization problems, interaction, and more. Yet the framework of decision problems turn out to be surprisingly expressive, and we will often use it in this book. 1.5.3 Edmonds’ quote We conclude this section with a quote from Edmonds [Edm65], that in the paper showing a polynomial-time algorithm for the maximum matching problem, explained the meaning of such a result as follows: For practical purposes computational details are vital. However, my purpose is only to show as attractively as I can that there is an efficient algorithm. According to the dictionary, “efficient” means “adequate in operation or performance.” This is roughly the meaning I want in the sense that it is conceivable for maximum matching to have no efficient algorithm. ...There is an obvious finite algorithm, but that algorithm increases in difficulty exponentially with the size of the graph. It is by no means obvious whether or not there exists an algorithm whose difficulty increases only algebraically with the size of the graph. ...When the measure of problem-size is reasonable and when the sizes assume values arbitrarily large, an asymptotic estimate of ... the order of difficulty of an algorithm is theoretically important. It cannot be rigged by making the algorithm artificially difficult for smaller sizes. ...One can find many classes of problems, besides maximum matching and its generalizations, which have algorithms of exponential order but seemingly none better ... For practical purposes the difference between algebraic and exponential order is often more crucial than the difference between finite and non-finite. ...It would be unfortunate for any rigid criterion to inhibit the practical development of algorithms which are either not known or known not to conform nicely to the criterion. Many of the best algorithmic idea known today would suffer by such theoretical pedantry. ... However, if only to motivate the search for good, practical algorithms, it is important to realize that it is mathematically sensible even to question their existence. For one thing the task can then be described in terms of concrete conjectures. Web draft 2007-01-08 21:59