Event
Math and Stats Graduate Student Seminar
Friday, April 7, 2017 13:00
Burnside Hall
1025 (10th Floor) - Graduate Lounge, 805 rue Sherbrooke Ouest, Montreal, QC, H3A 0B9, CA
Ìý
Speaker
Alexander Brandts-Longtin
Ìý
Topic
Complexity Theory: NP completeness and reduction of problems.
I will define the complexity classes P, NP, NP-complete, and
NP-hard and show that many natural problems belong to
these classes. I will also discuss reductions between problems,
and show that some hard problems can be approximated
while others cannot.