Completeness NP- The hardest problems in NP. Complete ■Cook-Lein:SAT. Karp:21 other problems such as TSP are also NP-complete NP Later:thousands of NP- complete problems from various sciences. 15Completeness ◼ The hardest problems in NP. ◼ Cook-Levin: SAT. ◼ Karp: 21 other problems such as TSP are also NP-complete ◼ Later: thousands of NP￾complete problems from various sciences. NP P NP￾Complete 15