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.

Follow us on

Back to top