Computational Complexity

Data Semantics LAb, Wright State University, Dayton, Ohio

Spring 2016

Meeting Times

Tuesdays and Thursdays 12:30pm to 1:50pm, Russ 146
Exams: first exam February 16 (no material or notes allowed); second exam March 22 (open book: all class material and notes allowed; final exam in the exam week.
Study table: Mondays 3-5pm, Russ 417. If you need different appointments, contact David Carral at dcarralma@gmail.com. Please pick up David in Joshi 465. An extra study table will be on Tuesday January 19, 4-6pm, also in Russ 417.
Office Hours: Tuesdays 3-4pm, Joshi 483, email contact preferred. The office hour is not for content questions, for these go to the study table or ask in class. No office hour February 16, March 1, March 8 - please arrange a meeting by email if needed.

Course Materials

Required: Thomas S. Sudkamp, Languages and Machines, Addison Wesley, 3rd Edition, 2006.
We will mainly recap chapter 8, cover most of chapters 14 and 15, and cover parts of chapters 16 and 17, as time allows.
Supplementary: Michael R. Garey and David S. Johnson, Computers and Intractability, Freeman, 1979.

Slides and my personal manuscript will be posted here as they become available. However, relevant for the exams is the material presented in class. If you miss a class, it's your responsibility to get all missing information.

Downloads
draft manuscript (pdf)
slides 2016-01-14 (pdf)
Computability slides 1 (pdf)
Computability slides 2 (pdf)
Computability slides 3 (pdf)
Computability slides 4 (pdf)
Computability slides 5 (pdf)
Proof of Cook's Theorem slides (pdf)

See also the Spring 2012 lecture for the old material. This class will partly be very similar.

Evaluation
Best effort attempt on all homework (announced in class) required to be admitted to final exam.
First and second exam: 30% each; final exam: 40%.
Grading will follow a standard scale (A: 100-90, B: 89-80, C: 79-70, D: 69-60, F: 59-0)

Course Outline (tentative)

Week 1 Introduction. Big-O notation.
Week 2 Turing Machines and time complexity.
Week 3 Properties of complexity.
Week 4 Adequacy of the complexity notion.
Week 5 Mid-term exam.
Week 6 Turing computable functions.
Week 7 Decidability.
Week 8 Undecidability.
Week 9 Mu-recursive functions.
Week 10 Cook's Theorem.
Week 11 Is P=NP?
Week 12 NPI. The polynomial hierarchy.
Week 13 Beyond NP.
Week 14 What we have learned.

Back to my home page.