Office: TAY 3.134
Office Hours: MW 3:00-4:00, or by appointment.
Theory of Computing Blog Aggregator
P vs. NP poll
List of many NP-complete problems
Certificate definition of NL is Definition 4.17 (Chapter 4) in Arora & Barak's graduate-level textbook Computational Complexity: A Modern Approach.
Complexity of various games and puzzles
Manuel Blum's lecture notes (pages 3 and 4) contain a counting argument showing the existence of functions with exponential circuit complexity. Note that he allows arbitrary gates on 2 inputs, whereas we allow only AND, OR, and NOT.
Problem Set 1
Problem Set 2
Problem Set 3
Problem Set 4
Problem Set 5
Problem Set 6
Problem Set 7
Problem Set 8
Problem Set 9
Problem Set 10
|Exams:||The three exams will be held in class on the following dates: Exam 1 on Monday, February 22; Exam 2 on Wednesday, April 7; and Exam 3 on Wednesday, May 5. No make-up exams will be given, so plan accordingly. You may bring a single, 8.5x11 inch, handwritten sheet of paper (you may use both sides). No calculators are allowed (they won't be necessary).|