COMPSCI 534: Computational Complexity

Qualifying Exam Syllabus

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 qualifying exams main page