MTH 4360
Complexity and Computational M · 4 credits · Spring 2027
Requirements
Prerequisites: MTH 3150 and MTH 4320
About this course
Two fundamental questions arising in any problem are: Can this problem be solved using a given abstract machine? How much time and space are required to solve it? The theory of computational complexity provides tools for analyzing theminimal amount of computational resources that are needed for the algorithmic solution of a problem. In this course, we will discuss a variety of types of computational problems (decision, search, counting, and optimization) by introducing an array of complexity classes to capture problem types. We will use the notions of reduction and completeness to establish relationships between seemingly unrelated problems, classes, and resources.
Seat status as of Oct 2, 10:36 AM ET. Seats can change between refreshes.
Chill Rank compares professors using Rate My Professors reviews, from Chill to Brutal. What each rank means