Discrete Optimization Lecture 2: Decision Problems, Complexity classes. Philosophy of Duality

This is a lecture from the course "Discrete Optimization" at the University of Victoria taught in 2025. The topic of this lecture is Decision Problems, Complexity classes. Philosophy of Duality. We also briefly discuss the P vs NP problem. Lecture notes for this topic can be found at https://extremalcombinatorics.com/optimization/notes/sec_classesReductions.html and https://extremalcombinatorics.com/optimization/notes/sec_NPhard.html and https://extremalcombinatorics.com/optimization/notes/sec_optimizationIntro.html