Does P = NP? -- Course leader Tom Naps

Welcome to the course home page for the 2023 winter term OLLI course "P=NP: The Simple Equation with Million-Dollar Consequences", which will meet on Zoom for seven Thursdays from 10:00 - 11:30 beginning January 12. Feel free to contact me (thomas.naps@gmail.com) anytime you have questions or concerns about the course.

Here's an outline of what we'll be doing each week. Depending on the pace we set and your feedback to me, this "plan" is likely to evolve.

• Week 1: Computation - What is it? How to characterize its complexity?
• Week 2: Graph problems and algorithms
• Week 3: 1971 - Cook’s proof changes the name of the game in computational complexity
• Week 4: A closer look at what led to and what followed Cook’s Theorem
• Week 5: What would it mean to prove P ≠ NP and live in a P ≠ NP world?
• Week 6: What would it mean to prove P ≠ NP and live in a P ≠ NP world?
• Week 7: What would it mean to prove P = NP and live in a P = NP world? Final wrap-up