Learning Objectives: By the end of this course you will be able to i) define central complexity classes for resource-bounded Turing machines and circuits; ii) prove inclusion relationships among these classes; and iii) explain applications of intractibility in computer security.

Text: Introduction to the Theory of Computation, Michael Sipser, 3^rd ed., Cengage Learning, 2012.

Grading: There will be weekly homework assignments (which together count as 30% of the final grade), a midterm exam (30%), a final exam (30%), and a presentation (10%). Final grades will be assigned based on curving the total weighted scores.

No late homework will be accepted; no makeup or early exams will be given.
Requests for regrading will be considered only during the week following the return date.
Attendance is required. Please note that only class notes (not class recordings) will be made available online.
Academic Integrity: the penalty for cheating is a failing grade for the course, and the University may take further disciplinary action. All of the work that you turn in should be your own and not that of a classmate or copied from another source such as generative AI.
Discrimination, Harassment, and Sexual Misconduct (Title IX): Santa Clara University is committed to providing all students with a safe learning environment free of all forms of discrimination, sexual harassment, and sexual violence.
Accommodations for Pregnant and Parenting Students: Santa Clara University does not discriminate against any student on the basis of pregnancy or related medical conditions.
Office of Accessible Education: to request academic accommodations for a disability, students must contact the Disability Resources Office located in Daly Science 300, (408) 554-4109, oae@scu.edu. Students must provide documentation of a disability to Disability Resources prior to receiving accommodations.