CS 365: Models of Computation

University of Waterloo, Winter 2025

Overview / Preface to the Notes

What can computers do? In this course, we examine different mathematical formulations of this question and see how they lead to some surprisingly strong results (and to some remarkly stubborn open problems as well). In doing so, we explore six main topics:

Decidability. What problems can computers solve, even with unbounded resources?
Time Complexity. What problems can computers solve in a reasonable amount of time?
Circuit Complexity. What problems can reasonably simple computers solve?
Randomized Computation. How does the ability to flip a coin affect the power of computers?
Space Complexity. What problems can computers solve with a reasonable amount of memory?
Communication and Query Complexity. What problems can we solve with computers that are limited only in how much information they can inspect or share?

The lecture notes below contain the essential results that we cover in the class. But to keep them concise, only the fundamentals are included. They represent starting points for the discussions we hold in class and a reference for reviewing the lectures; not a self-contained complete introduction to the topic.

If you are enrolled in the class, you can find more information about the course itself in the official Learn page.

And if you are not enrolled in the class, you are most welcome to use these notes in your independent study as well. If you do and find them useful, please let me know! And because these notes are meant to complement the in-person lectures and discussions, you may find them most useful when combined with additional complementary resources. Luckily, there are many great resources (online and in the form of textbooks) available for this purpose.

Theoretical computer science is a rich area of mathematical research with many beautiful results and countless fascinating open problems. Hopefully, these notes will convey at least a bit of the interest in this area and leave you ready to continue studying more advanced topics in the field.

Happy explorations!

Eric Blais
Waterloo, ON, Canada
December 7, 2024

Lecture Notes

The preliminary version of the notes for each lecture are listed below. One word of warning: I will be updating these notes throughout the term with additions and corrections.

1. Introduction
2. Turing Machines
3. Decidable Languages
4. Recursion Theorem
5. Undecidability
6. Reductions
7. Time Complexity
8. P vs. NP
9. Polynomial Hierarchy
10. Boolean Circuits
11. Non-Uniform Computation
12. Boolean Formulas
13. Satisfiability
14. Randomized Computation
15. P vs. BPP
16. Randomized Verification
17. Space Complexity
18. Logarithmic Space
19. Sublogarithmic Space
20. Nonregular Languages
21. Communication Complexity