Complexity and Computability Final

Notes

• The emphasis of the final will be on complexity theory (i.e., Chapters 7, 8, 9.2 (including earlier stuff that these chapters refer to), homework, notes, and what we did in class), and on overview questions. You should still know the main points of computability theory.
• You do not have to memorize proofs, but you should know the main ideas of the proofs and you should understand the proofs from the book, the notes, and from class.
• Some example final question topics (not an exhaustive list):
  • Know and be able to show the relationships between different complexity classes (this includes classes like RE as well). Know which relationships are likely to hold, which relationships are possible but unlikely, and how these relationships inply each other (for example, P = NP implies NP = coNP).
  • Know and be able to show basic properties of complexity classes, like closure properties.
  • Be able to classify languages (both familiar languages and new ones) according to their complexity classes, and explain your classifications.
  • Be able to come up with simple reductions.
  • Be able to adapt familiar reductions. For example, since you have seen how to show that HALF-CLIQUE is NP-complete, you should also be able to show that QUARTER-INDEPENDENT-SET is NP-complete.
• The final will be closed book and notes, but you may bring one sheet of letter-sized paper with your own hand-written notes. You may write on both sides.
• Like the midterm, the final will consist of five or six questions of equal weight. Your lowest question score won't count.
• The final can not be made up except for real emergencies in which case proper documentation (like a doctor's note) will be required. If at all possible, you should contact me prior to the exam. Oversleeping, cars that don't start etc. do not constitute a valid excuse.

Complexity and Computability