Design and Analysis of Algorithms 4.NP and Computational Intractability Mingyu XIAO School of Computer Science and Engineering University of Electronic Science and Technology of China
Design and Analysis of Algorithms 4. NP and Computational Intractability Mingyu XIAO School of Computer Science and Engineering University of Electronic Science and Technology of China
Algorithm Design Patterns and Anti-Patterns Algorithm design patterns. Ex. Greedy. O(n log n)interval scheduling. Divide-and-conquer. O(n log n)FFT. Dynamic programming. O(n2)edit distance. Duality. O(n3)bipartite matching. Reductions. Algorithm design anti-patterns. NP-completeness. O(nc)algorithm unlikely. PSPACE-completeness. O(nc)certification algorithm unlikely. Undecidability. No algorithm possible. 3
2 Algorithm Design Patterns and Anti-Patterns Algorithm design patterns. Ex. Greedy. O(n log n) interval scheduling. Divide-and-conquer. O(n log n) FFT. Dynamic programming. O(n2) edit distance. Duality. O(n3) bipartite matching. Reductions. Algorithm design anti-patterns. NP-completeness. O(nc ) algorithm unlikely. PSPACE-completeness. O(nc ) certification algorithm unlikely. Undecidability. No algorithm possible
4.1 Polynomial-Time Reductions
4.1 Polynomial-Time Reductions
Classify Problems According to Computational Requirements Q.Which problems will we be able to solve in practice? A working definition.[von Neumann 1953,Godel 1956,Cobham 1964,Edmonds 1965,Rabin 1966] Those with polynomial-time algorithms. Yes Probably no Shortest path Longest path Matching 3D-matching Min cut Max cut 2-SAT 3-SAT Planar 4-color Planar 3-color Bipartite vertex cover Vertex cover
4 Classify Problems According to Computational Requirements Q. Which problems will we be able to solve in practice? A working definition. [von Neumann 1953, Godel 1956, Cobham 1964, Edmonds 1965, Rabin 1966] Those with polynomial-time algorithms. Yes Probably no Shortest path Longest path Min cut Max cut 2-SAT 3-SAT Matching 3D-matching Planar 4-color Planar 3-color Bipartite vertex cover Vertex cover
Classify Problems Classes.Classify problems according to those that can be solved in polynomial-time and those that cannot. Frustrating news.Huge number of fundamental problems have defined classification for decades. This chapter.Show that these fundamental problems are "computationally equivalent"and appear to be different manifestations of one really hard problem. 5
5 Classify Problems Classes. Classify problems according to those that can be solved in polynomial-time and those that cannot. Frustrating news. Huge number of fundamental problems have defined classification for decades. This chapter. Show that these fundamental problems are "computationally equivalent" and appear to be different manifestations of one really hard problem