CSCI 384 - Complexity Theory

FC NSMA QFR

4 credits
This is a continuation of CSCI 383, in which we mapped out the world in terms of what computers can and cannot do. In this course, we will classify problems based on the resources that are needed to solve them and how these resources relate to the needs of other problems. We will consider questions such as: How much time or memory does a computer need to solve a problem? Does randomness help us solve problems faster? If you don’t trust someone, what can they convince you of?

Prerequisites: CSCI 383.