Data Structures and Algorithms13 Hard or Intractable ProblemsIf a problem has an O(nk) time algorithm (where k is a constant), then weclass it as having polynomial time complexity and as being efficientlysolvable.If there is no known polynomial time algorithm, then the problem is classedas intractable.The dividing line is not always obvious. Consider two apparently similarproblems:        Euler's problem                 asks whether there is a        (often characterized as the     path through a graph which        Bridges of K鰊igsberg - a       traverses each edge only        popular 18th C puzzle)          once.        Hamilton's problem              asks whether there is a                                        path through a graph which                                        visits each vertex exactly                                        once.Euler's problem        The 18th century German city of K鰊igsberg was situated on the        river Pregel. Within a park built on the banks of the river, there [Image]were two islands joined by seven bridges.        The puzzle asks whether it is possible to take a tour through the        park, crossing each bridge only once.An exhaustive search requires starting at every possible point andtraversing all the possible paths from that point - an O(n!) problem.However Euler showed that an Eulerian path existed iff   * it is possible to go from any vertex to any other by following the     edges (the graph must be connected) and   * every vertex must have an even number of edges connected to it, with at     most two exceptions (which constitute the starting and ending points).It is easy to see that these are necessary conditions: to complete the tour,one needs to enter and leave every point except the start and end points.The proof that these are sufficient conditions may be found in theliterature . Thus we now have a O(n) problem to determine whether a pathexists.   Transform the map into a        graph in which         We can now easily see that the Bridges of the nodes represent the "dry  K鰊igsberg does not have a solution.         land" points  and the arcs represent the   A quick inspection shows that it does have a           bridges.            Hamiltonian path.            [Image]     However there is no known efficient algorithm for determining     whether a Hamiltonian path exists.But if a path was found, then it can be verified to be a solution inpolynomial time: we simply verify that each edge in the path is actually anedge (O(e) if the edges are stored in an adjacency matrix) and that eachvertex is visited only once (O(n2) in the worst case).Classes P and NP                               What does NP mean?                               At each step in the algorithm, you guess                               which possibility to try next. This is the                               non-deterministic part: it doesn't matter Euler's problem lies in the   which possibility you try next. There is no class P: problems solvable in information used from previous attempts Polynomial time. Hamilton's   (other than not trying something that you've problem is believed to lie in already tried) to determine which class NP (Non-deterministic   alternative should be tried next. However, Polynomial).                  having made a guess, you can determine in                               polynomial time whether it is a solution or Note that I wrote "believed"  not. in the previous sentence. No-one has succeeded in       Since nothing from previous trials helps you proving that efficient (ie    to determine which alternative should be polynomial time) algorithms   tried next, you are forced to investigate don't exist yet!              all possibilities to find a solution. So the                               only systematic thing you can do is use some                               strategy for systematically working through                               all possibilities, eg setting out all                               permutations of the cities for the                               travelling salesman's tour.Many other problems lie in class NP. Some examples follow.Composite NumbersDetermining whether a number can be written as the product of two othernumbers is the composite numbers problem. If a solution is found, it issimple to verify it, but no efficient method of finding the solution exists.AssignmentAssignment of compatible room-mates: assume we have a number of students tobe assigned to rooms in a college. They can be represented as the verticeson a graph with edges linking compatible pairs. If we have two per room, aclass P algorithm exists, but if three are to be fitted in a room, we have aclass NP problem.Boolean satisfiabilityGiven an arbitrary boolean expression in n variables:     a1 op a2 op ... op anwhere op are boolean operators, and, or, ..Can we find an assignment of (true,false) to the ai so that the expressionis true? This problem is equivalent to the circuit-satisfiability problemwhich asks can we find a set of inputs which will produce a true at theoutput of a circuit composed of arbitrary logic gates.A solution can only be found by trying all 2n possible assignments.Map colouring The three-colour map colouring problem asks if we can colour a map so that no adjoining countries have the same colour. Once a solution has been guessed, then it is readily proved. [This problem is easily answered if there are only 2 colours -     [Image] there must be no point at which an odd number of countries meet - or 4 colours - there is a proof that 4 colours suffice for any map.]This problem has a graph equivalent: each vertex represents a country and anedge is drawn between two vertices if they share a common border.Its solution has a more general application. If we are scheduling work in afactory: each vertex can represent a task to be performed - they are linkedby an edge if they share a common resource, eg require a particular machine.A colouring of the vertices with 3 colours then provides a 3-shift schedulefor the factory.Many problems are reducible to others: map colouring can be reduced to graphcolouring. A solution to a graph colouring problem is effectively a solutionto the equivalent map colouring or scheduling problem. The map orgraph-colouring problem may be reduced to the boolean satisfiabilityproblem. To give an informal description of this process, assume the threecolours are red, blue and green. Denote the partial solution, "A is red" byar so that we have a set of boolean variables:                               ar  A is red                               ab  A is blue                               ag  A is green                               br  B is red                               bb  B is blue                               bg  B is green                               cr  C is red                               ... ...Now a solution to the problem may be found by finding values for ar, ab, etcwhich make the expression true:     ((ar and not ab and not ag) and ( (bb and (cb and (dg ....Thus solving the map colouring problem is equivalent to finding anassignment to the variables which results in a true value for the expression- the boolean satisfiability problem.There is a special class of problems in NP: the NP-complete problems. Allthe problems in NP are efficiently reducible to them. By efficiently, wemean in polynomial time, so the term polynomially reducible provides a moreprecise definition.In 1971, Cook was able to prove that the boolean satisfiability problem wasNP-complete. Proofs now exist showing that many problems in NP areefficiently reducible to the satisfiability problem. Thus we have a largeclass of problems which will are all related to each other: finding anefficient solution to one will result in an efficient solution for them all.An efficient solution has so far eluded a very large number of researchersbut there is also no proof that these problems cannot be solved inpolynomial time, so the search continues.Class NP problems are solvable by non-deterministic algorithms: thesealgorithms consist of deterministic steps alternating with non-deterministicsteps in which a random choice (a guess) must be made. A deterministicalgorithm must, given a possible solution,   * have at least one set of guessing steps which lead to the acceptance of     that solution, and   * always reject an invalid solution.We can also view this from the other aspect: that of trying to determine asolution. At each guessing stage, the algorithm randomly selects anotherelement to add to the solution set: this is basically building up a "game"tree. Various techniques exist for pruning the tree - backtracking when aninvalid solution is found and trying another branch, but this is where theexponential time complexity starts to enter!Travelling salesmanIt's possible to cast this problem - which is basically an optimality one,we're looking for the best tour - into a yes-no one also by simply asking:     Can we find a tour with a cost less than x?By asking this question until we find a tour with a cost x for which theanswer is provably no, we have found the optimal tour. This problem can alsobe proved to be in NP. (It is reducible to the Hamiltonian circuit problem.)Various heuristics have been developed to find near optimal solutions withefficient algorithms.One simple approach is the find the minimum spanning tree. One possible toursimple traverses the MST twice. So we can find a tour which is at most twiceas long as the optimum tour in polynomial time. Various heuristics can nowbe applied to reduce this tour, eg by taking shortcuts.An algorithm due to Christofides can be shown to produce a tour which is nomore than 50% longer than the optimal tour.        It starts with the MST and singles out all cities which are linked [Image]to an odd number of cities.        These are linked in pairs by a variant of the procedure used to        find compatible room-mates. [Image]This can then be improved by taking shortcuts.Another strategy which works well in practice is to divide the "map" intomany small regions and to generate the optimum tour by exhaustive searchwithin those small regions. A greedy algorithm can then be used to link theregions. While this algorithm will produce tours as little as 5% longer thanthe optimum tour in acceptable times, it is still not guaranteed to producethe optimal solution. Key termsPolynomial Time Complexity     Problems which have solutions with time complexity O(nk) where k is a     constant are said to have polynomial time complexity.Class P     Set of problems which have solutions with polynomial time complexity.Non-deterministic Polynomial (NP)     A problem which can be solved by a series of guessing     (non-deterministic) steps but whose solution can be verified as correct     in polynomial time is said to lie in class NP.Eulerian Path     Path which traverses each arc of a graph exactly once.Hamiltonian Path     Path which passes through each node of a graph exactly once.NP-Complete Problems     Set of problems which are all related to each other in the sense that     if any one of them can be shown to be in class P, all the others are     also in class P. Continue on to Games                 Back to the Table of Contents