Intractable Problems

Welcome to week 9!

Learning objectives

By the end of this week, you will be able to:

• Describe the difference between problems in various complexity classes
• Explain the traveling salesman problem and solve it using naive and approximation algorithms
• Recognize the challenges in solving whether P = NP

What's due this week

• Week 9 Quiz (on Gradescope), due Thursday before class starts
• Assignment 5, due Sunday