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 cover4 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