1610906232-7ba7dbaea13262b50a6029d682cb7f1b (824370), страница 59
Текст из файла (страница 59)
Arguably, an average-case approach -for example, insisting that thetime requirements of a Turing machine, when averaged over all possible inputsof length n, be bounded by p(n)- would be a better predictor of the practicalutility of the algorithm. Although average-case analysis seems a very reasonablealternative, it is in fact itself open to even more devastating challenges. Forexample, which distribution on the inputs should we adopt in our average-caseanalysis? There seems to be no satisfactory answer.Despite these reservations, however, polynomially bounded computation isan appealing and productive concept, and it leads to an elegant and useful theory.By focusing on the gray areas on its boundary, one often forgets what a usefulclassification tool it is, that it includes mostly practically feasible algorithms,and excludes mostly impractical ones.
But the best way to get acquainted withpolynomial-time computation, its true scope, and its limitations, is to introducea variety of interesting computational problems that are known to belong in P.It is also instructive to contrast such problems with certain examples of stubbornproblems that do not seem to be in P. Often the difficult and the easy problemslook very similar.We have already seen some very interesting specimens and subclasses of P.For example, all regular languages and all context-free languages belong there(recall Theorems 2.6.2 and 3.6.1, part (c)). We also know that the refiexivetransitive closure of a relation can be computed in polynomial time (Section1.6). We next examine an interesting variant of this latter problem.The reachability problem is the followingREACHABILITY: GivenadirectedgraphG ~ VxV, where V = {Vl,""V n }is a finite set, and two nodes Vi,Vj E V, is there a path from Vi to Vj?(All graphs mentioned in the context of computational problems are, of coursefinite.) Is REACHABILITY in P? Strictly speaking, since P contains only languages, REACHABILITY has no business there.
REACHABILITY is what we calla problem. A problem is a set of inputs, typically infinite, together with ayes-or-no question asked of each input (a property an input mayor may nothave). In the example of REACHABILITY the set of inputs is the set of all triples(G, Vi, Vj), where G is a finite graph, and Vi, Vj are two nodes of G. The questionasked is whether there is a path from Vi to Vj in G.This is not the first time that we see problems. The HALTING PROBLEMis definitely a problem: Its inputs are Turing machines and strings, and thequestion asked is whether the given Turing machine halts when started on thisinput string:HALTING PROBLEM:AI accept w?Given a Turing machine M and an input string w, does280Chapter 6: COMPUTATIONAL COMPLEXITYIn Chapter 5 we studied the HALTING PROBLEM in terms of its "linguistic surrogate," the languageH = {"M" "w" : Turing machine M halts on string w}.Similarly, we can study the REACHABILITY problem in terms of the languageR = {t;;(G)b(i)b(j): There is a path fromVitoVjin G},where b(i) denotes the binary encoding of integer i, and t;; is some reasonableway of encoding graphs as strings.
Several natural encodings of graphs cometo mind. Let us agree to encode a graph G ~ V x V by its adjacency matrix,linearized as a string (recall Example 4.4.3 and Figure 4-21). One of the mainpoints that will emerge from the discussion that follows is that the precise detailsof encodings rarely matter.Languages encode problems. But of course also any language L ~ ~* canbe thought of as a problem:THE DECISION PROBLEM FOR L: Given a string x E ~*, is x E L?It is productive to think of a problem and the associated language interchangeably.
Languages are more appropriate in connection to Turing machines, whileproblems are more clear statements of practical computational tasks of interest,for which we must develop algorithms. In the following pages we shall introduceand discuss extensively many interesting problems; we shall treat a problem andthe corresponding language as two different aspects of the same thing. For example, we shall next point out that REACHABILITY is in P. By this we meanthat the corresponding language R, defined above, is in P.Indeed, REACHABILITY can be solved by first computing the reflexivetransitive closure of G, in time O(n 3 ) by the random access Turing machineof Example 4.4.3.
Inspecting the entry of the reflexive-transitive closure of Gthat corresponds to Vi and Vj would then tell us whether there is a path fromVi to Vj in G. Since we know that random access machines can be simulated byordinary Turing machines in polynomial time, it follows that REACHABILITY isin P.Notice that, since we are only interested in determining whether the timebound is or is not a polynomial, we felt free to express it as a function not of thelength of the input, which is m = 1t;;(G)b(i)b(j)I, but as a function of n = lVI,the number of nodes: Since it is easy to see that m = O(n 3 ), this is yet anotherinconsequential inaccuracy, one that will not interfere with the issues that wedeem important.Eulerian and Hamiltonian GraphsHistorically the first problem concerning graphs, studied and solved by the greatmathematician of the eighteenth century Leonard Euler, is this:2816.2: Problems, problems ...EULER CYCLE: Given a graph G, is there a closed path in G that uses eachedge exactly once?The path sought can go through each node many times (or evenif the graph has isolated nodes, nodes without edges in or out ofgraph that contains such a path is called Eulerian or unicursal.ple.
the graph shown in Figure 6-1(a) is Eulerian while the graph6-1(b) is not.not at all,them). AFor examin Figure I(b)(a)Figure 6-1It is not difficult to see that EULERcourse, that the corresponding languageCYCLEis in P -by this we mean, ofL = {I£( G) : G is Eulerian}is in P. This follows from the following neat characterization of Eulerian graphsdue to, well, Euler.
Call a node in a graph isolated if and only if it has no edgesincident upon it.A graph G is Eulerian if and only if it has the following two properties:(a) For any pair of nodes u, v E V neither of whieh is isolated, there is a pathfrom u to v; and(b) All nodes have equal numbers of incoming and outgoing edges.It is rather immediate that both conditions are necessary for the graph tobe Eulerian. We leave the proof of sufficiency as an exercise (Problem 6.2.1).It is thus very easy to test whether a graph is Eulerian: We first make surethat all nodes, except for any isolated ones, are connected; this can be done inpolynomial time by computing the reflexive-transitive closure of the graph, and282Chapter 6: COMPUTATIONAL COMPLEXITYthen testing whether all nodes except for the isolated ones are connected in allpossible ways (after all, the reflexive-transitive closure of a graph contains theanswer to all possible connectivity questions on the graph).
We know that thereflexive-transitive closure can be computed in a polynomial number of steps.We then test whether all nodes have an equal number of incoming and outgoingedges -this can be obviously done in polynomial time as well.Incidentally, this is an instance of a pattern that will be repeated ad nauseamin the next pages: We show that a problem (EULER CYCLE) is in P by using thepreviously established fact that another problem (in our case REACHABILITY)in P -that is, by reducing it to an already solved problem.Perhaps the main point of this and the next chapter is that there are manynatural, decidable, simply stated problems that are not known 01' believed to bein P. Very often, such a problem is very similar to another that is known to bein P! Consider, for example, the following problem, studied by another famousmathematician, this time of the nineteenth century, William Rowan Hamilton-and many mathematicians after him:HAMILTON CYCLE: Given a graph G, is there a cycle that passes througheach node of G exactly once?Such a cycle is called a Hamilton cycle, and a graph that has one is calledHamiltonian.
Notice the difference: Now it is the nodes, not the edges, thatmust be traversed exactly once; not all edges need be traversed. For example,the graph in Figure 6-1(b) is Hamiltonian but not Eulerian, while the one inFigure 6-1(a) is both Eulerian and Hamiltonian.Despite the superficial similarity between the two problems EULER CYCLEand HAMILTON CYCLE, there appears to be a world of difference between them.After one and a half centuries of scrutiny by many talented mathematicians, noone has discovered a polynomial algorithm for HAMILTON CYCLE.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
