Complexity and Computability

Lectures: Tuesday-Thursday 14:20 – 15:40  (Caldwell Lab 220)

Midterm: Thursday October 3rd
— Midterm – Solutions
— Median: 74 — Average: 65.5 — Max possible: 100,
— Median with Bonus: 80 — Average with Bonus: 70.8 — Max possible with Bonus: 110

Instructor:  Pooya Hatami (Dreese Lab 489,
TA:  Minghao Tian (Dreese Lab 474,

Office Hours:
Pooya Hatami: Tuesdays 17:00-18:00 (Dreese 489) or by appointment
Minghao Tian: Wednesdays 16:00-17:00 (Dreese 474)

Lecture Notes

I will maintain the pdf file below, gradually adding new lectures:

Lectures 1-22 (last updated Nov 10)


Assignment #1, due September 10th at the start of class,
        Assignment#1 — Solutions
        Total points possible: 100/100, Median: 78/100
Assignment #2, due October 3rd at the start of class
        Assignment#2 – Solutions
        Note: HW2.7 is now a bonus problem worth 10 points
        Total points possible: 85/85, Median: 55.5/85=65/100
Assignment #3 due November 26th at the start of class

Course Summary (tentative):

  • This course intends to introduce the student to theory of computability, and computational complexity theory, with a slight more emphasis on the latter.
  • Computability Theory: Notions of algorithms, Turing Machines (deterministic, nondeterministic, …), Church-Turing Thesis,  Decidability, Turing-recognizability and Enumerability, Diagonilization, Reducibility
  • Complexity Theory: Complexity classes and measures, P, NP, coNP,  NP-completeness, Hierarchy Theorems, Space Complexity, Boolean circuits, randomized computation, RP, ZPP, BPP, RL, BPL

Related Reading: 

25% homeworks — 30% midterm — 45% last exam

Policy on Collaboration:
Studying in groups is encouraged, however we also encourage students to work on the current homework set on their own. If you do collaborate, state it clearly at the beginning of your solution (give name of collaborator). Acknowledged collaboration does not mean copying someone else’s solution: Discuss the solutions, understand the ideas and give your own rendering.