1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 58
Текст из файла (страница 58)
This is surely the kind of task that you would liketo use a computer to solve. And, from a theoretical standpoint, the problem iscertainly solvable. If there are n cities to visit, the number of possible itinerariesis finite -to be precise, (n-1)!, that is, 1·2·3··· (n-1). Hence an algorithm caneasily be designed that systematically examines all itineraries in order to findthe shortest.
Naturally, one can even design a Turing machine that computesthe shortest tour.Still, one gets an uneasy feeling about this algorithm. There are too manytours to be examined. For our modest problem of 10 cities, we would have toexamine 9! = 362,880 itineraries. With some patience, this can be carried outby a computer, but, what if we had 40 cities to visit? The number of itinerariesis now gigantic: 39!, which is larger than 10 45 . Even if we could examine 10 15tours per second -a pace that is much too fast even for the most powerful275276Chapter 6: COMPUTATIONAL COMPLEXITYsupercomputers, existing or projected -the required time for completing thiscalculation would be several billion lifetimes of the universe!Evidently, the fact that a problem is solvable in theory does not immediately imply that it can be solved realistically in practice.
Our goal in thischapter is to develop a formal mathematical theory -a quantitative refinementof the Church-Turing thesis- that captures this intuitive notion of "a practically feasible algorithm." The question is, which algorithms - -and which Turingmachines- - should we consider as practically feasible?As the introductory example of the TRAVELING SALESMAN PROBLEM reveals, the limiting parameter here is the time or number of steps required bythe algorithm on a given input. The (n - I)! algorithm for the TRAVELINGSALESMAN PROBLEM was deemed unrealistic exactly because of the excessiveexponential growth of its time requirements (it is easy to see that the function(n -I)! grows even faster than 2n). In contrast, an algorithm with a polynomialrate of growth, like the algorithms we have developed in various parts of thisbook, would obviously be much more attractive.It seems that, in order to capture the notion of "practically feasible algorithm" we must limit our computational devices to only run for a number ofsteps that is bounded by a polynomial in the length of the input.
But whichcomputational devices exactly should we choose as the basis of this importanttheory? The Turing machine, its multitape variant, the multidimensional one,or perhaps the random access model? The simulation results in Section 4.3tell us that, since we are interested in polynomial growths, the choice does notmatter -as long as we leave out the nondeterministic model with its apparentexponential power, recall Section 4.5 and see Section 6.4. If a Turing machine ofanyone of these deterministic kinds halts after a polynomial number of steps,there is an equivalent Turing machine of any other kind which also halts after apolynomial number of steps -only the polynomials will differ. So we might aswell settle on the simplest model, the standard Turing machine. This "modelindependence" is an important side benefit of the choice of the polynomial ratesof growth as our concept of "efficiency."We are therefore led to the following definition:Definition 6.1.1: A Turing machine M = (K,"Y:., 15, s, H) is said to be polynomially bounded if there is a polynomial p(n) such that the following is true:For any input x, there is no configuration C such that (s, l>!Jx) f-~Ixll+l C.
Inother words, the machine always halts after at most p(n) steps, where n is thelength of the input.A language is called polynomially decidable if there is a polynomiallybounded Turing machine that decides it. The class of all polynomially decidablelanguages is denoted P.6.1: The Class P277Our quantitative refinement of the Church-Turing thesis can now be statedas follows: Polynomially bounded Turing machines and the class P adequatelycapture the intuitive notions, respectively, of practically feasible algorithms andr-ealistically solvable problems.In other words, we are proposing P as the quantitative analog of the classof recursive languages.
In fact, P does indeed have some of the properties of theclass of recursive languages:Theorem 6.1.1: P is closed under complement.Proof: If a language L is decidable by a polynomially bounded Turing machineM, then its complement is decided by the version of M that inverts y and n.Obviously, the polynomial bound is unaffected .•Moreover, we can use diagonalization to exhibit certain simple recursivelanguages that are not in P.
Consider the following quantitative analog of the"halting" language H (recall Section 5.3):E = {"M" "w" : M accepts input w after at most 21wl steps}.Theorem 6.1.2: Ef. P.Proof: The proof mimics rather faithfully that of the undecidability of thehalting problem (Theorem 5.3.1). Suppose that E E P. Then the followinglanguage is also in P:E1 ={"M" : M accepts "M" after at most 2I" M "1 steps},and, by Theorem 6.1.1 so is its complement, E 1 . Therefore, there is a Turingmachine M* accepting all descriptions of Turing machines that fail to accepttheir own description within time 2n (where n is the length of the description);M* rejects all other inputs. Furthermore, M* always halts within p(n) steps,where p(n) is a polynomial.
We can assume that M* is a single-tape machinebecause, otherwise, it can be converted to one with no loss of the polynomialproperty.Recall that, since p(n) is a polynomial, there is a positive integer no suchthat p(n) ~ 2n for all n 2 no. Furthermore, we can assume that the length ofthe encoding of M* is at least no, that is, I"M*" I 2 n~. If not, we can add toM* no useless states that are never reached in a computation.The question is now this: What does M* do when presented with its owndescription, "M*"? Does it accept or reject? (It was constructed so that it doesone of the two.) Both answers lead to a contradiction: If M* accepts "M*" ,then278Chapter 6: COMPUTATIONAL COMPLEXITYsince M* decides E l , this means that M* does not accept "M*" within 21"M*"1steps; but M* was constructed so that it always halts within p( n) steps on inputsof length n, and 2I" M* " 1 > p( I" M*" !); so it must reject.
Similarly, by assumingthat M* rejects its own description, we deduce that it accepts it. Since the onlyassumption that led to this contradiction was that E E P, we must concludethat E f. P .•Problems for Section 6.16.1.1. Show that P is also closed under union, intersection, and concatenation.6.1.2. Show that P is closed under Kleene star. (This is harder than the proofsof the closure properties in the previous problem. To tell whether x E L*for some L E P, you have to consider all substrings of x, starting with theones of length one and progressing towards longer and longer ones -verymuch like the dynamic programming algorithm for context-free recognition;recall Section 3.6.)BPROBLEMS, PROBLEMS ...How well does the class P capture the intuitive notion of "satisfactorily solvableproblem?" How widely accepted is the thesis that polynomial algorithms areprecisely the empirically feasible ones? It is fair to say that, while it is the onlyserious proposal in this arena, it can be challenged on various grounds t.
Forexample, it can be argued that an algorithm with time requirements n lOO , oreven IO lOO n 2 , is not at all "practically feasible," even though it is a polynomialtime one. Also, an algorithm with time requirements nloglogn may be consideredperfectly feasible in practice, despite the fact that its growth is not bounded byany polynomial. The empirical argument in defense of our thesis is that suchextreme time bounds, though theoretically possible, rarely come up in proctice:Polynomial algorithms that arise in computational practice usually have smallexponents and palatable constant coefficients, while nonpolynomial algorithmsare usually hopelessly exponential, and are therefore of quite limited use inpractice.tBut even the Church-Turing thesis was challenged extensively during its time,and in fact from both sides: There were mathematicians who thought that Turingdecidability is too restricted a notion, while others opined that it is too liberal.In fact, complexity theory, the subject of this and the next chapter, can be seenas the latest and most serious challenge of the latter type.6.2: Problems, problems ...279A further criticism of our thesis is that it categorizes an algorithm basedonly on its worst-case performance (the largest running time over all inputs oflength n).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
