In your journey through computation, you likely have noticed that many problems can be solved with the same solution through a skill you have honed called abstraction. Through this process, you may have noticed more nuanced connections between problems. Some problems require some translation before being solved using the solution to another problem. Other problems are immune to this sort of transformation and feel fundamentally more difficult than others. Some problems feel downright impossible to solve—are they actually impossible?
In this course, we study the theory of computation where we use mathematics to model problems of increasing complexity and study their relationships with each other. By going through this modeling process, we can:
- Deeply understand a problem and its potential corner cases.
- Prove properties of a problem, e.g., the correctness of candidate solutions.
- Reduce a problem to another problem, i.e, formally solve one problem in terms of another.
- Categorize a problem as easier or harder than other problems in a precise way.
By the end of the course, we will explore the limits of computation. Are there problems that are intractable in practice? Are there problems that can provably never have a solution?
