Complexity and Computability (Spring 21)


Instructor:  Pooya Hatami (last_name.2@osu.edu)
Grader info: Jack DePascale (last_name.9@osu.edu)

Lectures:

  • Tuesday-Thursday 14:20 – 15:40
  • Zoom Info can be found on Carmen
  • Lectures will be live on zoom (the recording will also be made available on Carmen). 
  • In some occasions we may have pre-recorded (not live) lectures posted on Carmen. Make sure to check your emails for such announcements. 

Office Hours:
Pooya Hatami: Thursdays 4:00pm-5:30pm (Zoom info on Carmen)


Lecture Notes (click here)

Above I will maintain a pdf of the notes of the covered material. 


Homework Assignments

There will be four homework-sets which will be posted on Carmen and solutions should be posted as a pdf file on Carmen.  The homework will be graded based on correctness rather than effort alone.


Course Summary (tentative):

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

Suggested Reading: 

The OSU Bookstore link for both books: https://tinyurl.com/W21-CSE-6321-34455


Grading: The grades will be based on 4 homework-assignments and one take-home final exam. There will be no midterm or final exams.

76% Homeworks + 24% Final Exam. 


Prerequisites:
CSE 3321/5321 “Automata and Formal Languages” (625) or equivalent or consent of instructor. Automata theory, mathematical background/maturity (Chapter 0 of Sipser’s book: mathematical proof, by contradiction, by induction, sets, relations, functions, cardinality).

This is a rigorous course with an emphasis on mathematical proofs. We assume familiarity with reading, writing, and coming up with formal mathematical proofs. 


Policy on Collaboration:
Studying in groups is encouraged, however we encourage you to work on the homework-assignments on your own. If you do collaborate, state it clearly at the beginning of your solution (give name of collaborator for each problem, even if you were the one helping someone.). Acknowledged collaboration does not mean copying someone else’s solution: Discuss ideas not the final solutions, use the ideas to solve the problems yourself and then write your own rendering.