SAT Clique ● Subset Sum ● TSP NP- Vertex Cover Integer Programming Complete Not known to be in P or NP-complete: · Factoring ·Graph Isomorphism Nash Equilibrium NP Local Search Shortest Path MST Maximum Flow Maximum Matching PRIMES Linear Programming 17NP P NP￾Complete • SAT • Clique • Subset Sum • TSP • Vertex Cover • Integer Programming • Shortest Path • MST • Maximum Flow • Maximum Matching • PRIMES • Linear Programming Not known to be in P or NP-complete: • Factoring • Graph Isomorphism • Nash Equilibrium • Local Search 17