MIT OpenCourseWare http ocw mit edu 6 006 Introduction to Algorithms Spring 2008 For information about citing these materials or our Terms of Use visit http ocw mit edu terms Lecture 14 Searching III 6 006 Spring 2008 Lecture 14 Searching III Toplogical Sort and NP completeness Lecture Overview Search 3 of 3 NP completeness BFS vs DFS job scheduling topological sort intractable problems P NP NP completeness Readings CLRS Sections 22 4 and 34 1 34 3 at a high level Recall Breadth First Search BFS level by level Depth First Search DFS backtrack as necc both O V E worst case time optimal BFS computes shortest paths min edges DFS is a bit simpler has useful properties 1 Lecture 14 Searching III 6 006 Spring 2008 Job Scheduling Given Directed Acylic Graph DAG where vertices represent tasks edges represent dependencies order tasks without violating dependencies 8 G H 7 I 4 A 9 2 3 C B D F E 6 5 Figure 1 Dependence Graph Source Source vertex with no incoming edges schedulable at beginning A G I Attempt BFS from each source from A finds H B C F from D finds C E F from G finds H need to merge costly Figure 2 BFS based Scheduling 2 1 Lecture 14 Searching III 6 006 Spring 2008 Topological Sort Reverse of DFS nishing times time at which node s outgoing edges nished Exercise prove that no constraints are violated Intractability DFS BFS are worst case optimal if problem is really graph search to look at graph what if graph is implicit has special structure is in nite The rst 2 characteristics implicitness and special structure apply to the Rubik s Cube problem The third characteristic in niteness applies to the Halting Problem Halting Problem Given a computer program does it ever halt stop decision problem answer is YES or NO UNDECIDABLE no algorithm solves this problem correctly in nite time on all inputs Most decision problems are undecidable program binary string nonneg integer decision problem a function from binary strings to YES NO Binary strings refer to nonneg integers while YES NO 0 1 in nite sequence of bits real number non assignment of unique nonneg integers to real numbers uncountable not nearly enough programs for all problems each program solves only one problem almost all problems cannot be solved 3 Lecture 14 Searching III 6 006 Spring 2008 n n n Rubik s cube n 2 or 3 is easy algorithmically O 1 time in practice n 3 still unsolved graph size grows exponentially with n solvability decision question is easy parity check nding shortest solution UNSOLVED n n Chess Given n n board some con guration of pieces can WHITE force a win can be formulated as graph search every algorithm needs time exponential in n EXPTIME complete Fraenkel Lichtenstein 1981 n2 1 Puzzle Given n n grid with n2 1 pieces sort pieces by sliding see Figure 3 similar to Rubik s cube solvability decision question is easy parity check nding shortest solution NP COMPLETE Ratner Warmuth 1990 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Figure 3 Puzzle 4 Lecture 14 Searching III 6 006 Spring 2008 Tetris Given current board con guration list of pieces to come stay alive NP COMPLETE Demaine Hohenberger Liben Nowell 2003 P NP NP completeness P all decision problems solvable by a polynomial O nc time algorithm e cient NP all decision problems whose YES answers have short polynomial length proofs checkable by a polynomial time algorithm e g Rubik s cube and n2 1 puzzle is there a solution of length k YES easy to check short proof moves Tetris NP but we conjecture Chess not NP winning strategy is big exponential in n P NP Big conjecture worth 1 000 000 generating proofs solutions is harder than checking them NP complete in NP NP hard NP hard as hard as every problem in NP every problem in NP can be e ciently converted into this problem if this problem P then P NP so probably this problem not in P 5
View Full Document
Unlocking...