Qualifying Exam Syllabus for COMPSCI 534: Computational Complexity

Exam is closed book.

Abstract Computing Models:

  • Finite State Automata and Regular Languages
  • Context Free Grammars Push Down Machines
  • Turing Machines and Counter Machines

Recursion Theory:

  • Recursive and Recursively Enumerable Languages
  • Undecidable Langauges, Diagonalization Proofs, Reducability
  • Church-Turing Thesis, Halting Problem 

Computational Complexity Theory:

  • Complexity Measures
  • Complexity Classes
  • Turing Machine Time and Space Complexity Classes

Intractability:

  • Polynomial Time and Log-Space Reductions
  • NP, NP-Completeness, and co-NP
  • PSPACE Complete Problems

Suggested Readings:

  • J. E. Hopcroft, R. Motwani, and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, 2nd ed., Addison Wesley
  • J. E. Hopcroft and J. D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison Wesley
  • M. Sipser, Introduction to the Theory of Computataion, PWS Publishers

Sample Exams:

 

Return to: Quals Home